Skip to content

Fibonacci Sequence

Fibonacci sequence and the golden ratio
FIBONACCI SEQUENCE
The Fibonacci sequence is defined by the recurrence
F0=0,F1=1,Fn+1=Fn+Fn−1.\begin{equation*}F_0 = 0,\qquad F_1 = 1,\qquad F_{n+1}=F_n+F_{n-1}.\end{equation*}
Thus each new term is obtained by adding the two previous terms.

The historical notes in this section follow Graham, Knuth, and Patashnik, Concrete Mathematics, Second Edition, Section 6.6.

The sequence is named after Leonardo Fibonacci, who introduced these numbers to Western European mathematics in 1202. Edouard Lucas studied the sequence extensively in the nineteenth century and helped popularize the term Fibonacci numbers. One of his amazing results was to use properties of Fibonacci numbers to prove that the 39-digit Mersenne number 2127−12^{127} - 1 is prime.
Fibonacci numbers appear in many different parts of mathematics. One famous early identity is due to the French astronomer Jean-Dominique Cassini, who presented it in 1680 [Cassini1733]:
Fn+1Fn−1−Fn2=(−1)n,n>0.\begin{equation*}F_{n+1}F_{n-1}-F_n^2=(-1)^n,\qquad n>0.\end{equation*}
For example, when n=6n=6, this gives
13⋅5−82=1.\begin{equation*}13\cdot 5 - 8^2 = 1.\end{equation*}
This identity is a first sign that the simple recurrence defining the Fibonacci sequence hides a rich algebraic structure.
Another important property is that Fibonacci numbers can be used to represent integers in a special way. Every positive integer can be written uniquely as a sum of nonconsecutive Fibonacci numbers. This result is known as Zeckendorf's theorem. For example,
1000000=832040+121393+46368+144+55.\begin{equation*}1000000 = 832040 + 121393 + 46368 + 144 + 55.\end{equation*}
In Fibonacci notation, this is
1000000=F30+F26+F24+F12+F10.\begin{equation*}1000000 = F_{30}+F_{26}+F_{24}+F_{12}+F_{10}.\end{equation*}
The condition that the Fibonacci numbers are nonconsecutive is essential for uniqueness: we are not allowed to use two neighboring Fibonacci numbers in the same representation.
The Fibonacci recurrence is linear, so it is natural to look first for solutions of the simpler form
an=rn\begin{equation*}a_n=r^n\end{equation*}
with r≠0r\neq 0. If this sequence satisfies the same recurrence an+2=an+1+ana_{n+2}=a_{n+1}+a_n, then
rn+2=rn+1+rn.\begin{equation*}r^{n+2}=r^{n+1}+r^n.\end{equation*}
Dividing by rnr^n gives the characteristic equation
r2=r+1⟹r2−r−1=0.\begin{equation*}r^2=r+1 \Longrightarrow r^2-r-1=0.\end{equation*}
By the quadratic formula, the two roots are
φ=1+52,ψ=1−52.\begin{equation*}\varphi=\frac{1+\sqrt5}{2},\qquad\psi=\frac{1-\sqrt5}{2}.\end{equation*}
The number φ\varphi is the golden ratio.
Both sequences φn\varphi^n and ψn\psi^n satisfy the Fibonacci recurrence. Since the recurrence is linear, adding two solutions, or multiplying a solution by a constant, produces another solution. Therefore every sequence of the form
Aφn+Bψn\begin{equation*}A\varphi^n+B\psi^n\end{equation*}
also satisfies it. We now choose AA and BB so that the initial values agree with F0=0F_0=0 and F1=1F_1=1.
From F0=0F_0=0, we get
0=Aφ0+Bψ0=A+B,\begin{equation*}0=A\varphi^0+B\psi^0=A+B,\end{equation*}
so B=−AB=-A. From F1=1F_1=1, we get
1=Aφ+Bψ=A(φ−ψ).\begin{equation*}1=A\varphi+B\psi=A(\varphi-\psi).\end{equation*}
But
φ−ψ=1+52−1−52=5⟹A=15 and B=−15.\begin{equation*}\varphi-\psi=\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}=\sqrt5 \qquad \Longrightarrow \qquad A=\frac{1}{\sqrt5} \quad \text{ and } \quad B=-\frac{1}{\sqrt5}.\end{equation*}
BINET'S FORMULA
Substituting these constants gives Binet's formula:
Fn=φn−ψn5=(1+52)n−(1−52)n5.\begin{equation*}F_n=\frac{\varphi^n-\psi^n}{\sqrt5}=\frac{\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n}{\sqrt5}.\end{equation*}
This closed formula was first published by Leonhard Euler in 1765 [Euler1765]. It was later rediscovered by Jacques Binet in 1843 [Binet1843], which is why the formula is now commonly called Binet's formula.

References

  • [GrahamKnuthPatashnik1994]Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. \textit{Concrete Mathematics: A Foundation for Computer Science}. Second edition. Addison-Wesley, 1994.
  • [Cassini1733]Cassini, Jean-Dominique. ``Une nouvelle progression de nombres.'' \textit{Histoire de l'Academie Royale des Sciences}, Paris, volume 1, 201. Presented in 1680 and published in 1733.
  • [Euler1765]Euler, Leonhard. ``Observationes analyticae.'' \textit{Novi commentarii academiae scientiarum imperialis Petropolitanae} 11 (1765), 124--143. Reprinted in \textit{Opera Omnia}, series 1, volume 15, 50--69.
  • [Binet1843]Binet, Jacques. ``Memoire sur l'integration des equations lineaires aux differences finies, d'un ordre quelconque, a coefficients variables.'' \textit{Comptes Rendus hebdomadaires des seances de l'Academie des Sciences} (Paris) 17 (1843), 559--567.