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

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

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