Fibonacci sequence

The Fibonacci sequence, discovered by Leonardo Pisano Fibonacci, begins

$$0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,\mathrm{\dots }$$

(Sequence http://www.research.att.com/projects/OEIS?Anum=A000045A000045 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({\varphi }^n-{\varphi }^{\prime n}\right)$$

called the Binet formula, where $\varphi$ denotes the golden ratio (and ${\varphi }^{\prime }$ is defined in the same entry). Note that

$$\underset{n\to \mathrm{\infty }}{lim}\frac{f_{n+1}}{f_n}=\varphi .$$