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},\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+\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.

Title example of closed form ExampleOfClosedForm 2013-03-22 15:03:07 2013-03-22 15:03:07 drini (3) drini (3) 4 drini (3) Example msc 11B99