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.

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