Fibonacci Numbers

Fibonacci numbers are defined by the following recurrance:

$ F_0\ =\ 0,$
$ F_1\ =\ 1,$
$F_i\ =\ F_{ i-1 } +\ F_{ i-2 }\ for\ i\geq 2.$

Each fibonacci number is the sum of the two previous ones, yielding the sequence

$0,1,1,2,3,5,8,13,21,34,55, \ldots$

Fibonacci numbers are related to the golden ratio $\phi$ and to its conjugate $\hat{\phi}$ which are the two roots of the equation:

$x^2\ =\ x\ +\ 1$

and are given by the following:

$ \phi = \frac{1+\sqrt{ 5 }}{2}$
$ \hat{ \phi } = \frac{1-\sqrt{ 5 }}{2} $

Where we have:

$F_i = \frac{\phi ^i-\hat{\phi}^i}{\sqrt{5}}$

Fibonacci numbers grow exponentially.