example of closed form

Consider the recurrence given by$x_0=7$ and $x_n=2x_{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},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+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n}{\sqrt{5}}.$$

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.