Consider the recurrence given by $x_0 = 7$ and $x_n = 2 x_{n-1}$ . Then it can be proved by induction that $x_n = 2^n\cdot 7$ .

The expression $x_n = 2^n \cdot 7$ is a closed form expression the recurrence given, since it depends exclusively on $n$ , whereas the recurrence depends on $n$ and $x_{n-1}$ (the previous value).

Now consider Fibonacci's recurrence: $$ f_n = f_{n-1}+ f_{n-2},\qquad f_0 = 1. $$

It is not a closed formula, since if we wanted to compute $f_{10}$ we would need to know $f_9$ , $f_8$ (and for knowing them, the previous terms too). However, such recurrence has a closed formula, known as Binet formula: $$ f_n = \frac{\left(\frac{1+\sqrt5}{2}\right)^n -\left(\frac{1-\sqrt5}{2}\right)^n }{\sqrt5}. $$ Binet formula is closed, since if we wanted to compute $f_n$ we only need to substitute $n$ on the previous formula, and no additional information is required.