# 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,\ldots$

(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(\phi^{n}-\phi^{\prime\;n}\right)$

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

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

## References

 Title Fibonacci sequence Canonical name FibonacciSequence Date of creation 2013-03-22 11:56:07 Last modified on 2013-03-22 11:56:07 Owner Koro (127) Last modified by Koro (127) Numerical id 21 Author Koro (127) Entry type Definition Classification msc 11B39 Synonym Fibonacci number Related topic HogattTheorem Related topic LucasNumbers Related topic ZeckendorfsTheorem Related topic ApplicationsOfSecondOrderRecurrenceRelationFormula Defines Binet formula