Fibonacci sequenceFibonacciSequence2001-11-04 07:34:092007-04-22 13:39:19DefinitionBinet formula\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic}The \emph{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 \PMlinkexternal{A000045}{http://www.research.att.com/projects/OEIS?Anum=A000045} in \cite{OEIS}).
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 \emph{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. $$
\begin{thebibliography}{15}
\bibitem{OEIS}
N. J. A. Sloane, (2004), The On-Line Encyclopedia of Integer Sequences, \PMlinkexternal{http://www.research.att.com/~njas/sequences/}{http://www.research.att.com/~njas/sequences/}.
\end{thebibliography}