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
Canonical name	ExampleOfClosedForm
Date of creation	2013-03-22 15:03:07
Last modified on	2013-03-22 15:03:07
Owner	drini (3)
Last modified by	drini (3)
Numerical id	4
Author	drini (3)
Entry type	Example
Classification	msc 11B99