The Fibonacci sequence, discovered by Leonardo Pisano Fibonacci, begins

$$ 0, 1, 1, 2, 3, 5 ,8 , 13, 21, 34, 55, 89, 144, 233, 377, \ldots $$

(Sequence A000045 in [1]). The $n$ th Fibonacci number is generated by adding the previous two. Thus, the Fibonacci sequence has the recurrence relation

$$ f_n = f_{n-1} + f_{n-2} $$

with $f_0=0$ and $f_1 = 1$ . This recurrence relation can be solved into the closed form

$$ f_n = \frac{1}{\sqrt{5}} \left( \phi^n - \phi'^{\;n} \right) $$ called the Binet formula, where $\phi$ denotes the golden ratio (and $\phi'$ is defined in the same entry). Note that

$$ \lim_{n\rightarrow \infty} \frac{f_{n+1}}{f_n} = \phi. $$

Bibliography

1

N. J. A. Sloane, (2004), The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/~njas/sequences/.