History and applications

Fibonacci numbers

The Fibonacci sequence

\[ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ \dots \]

was first discussed in Europe by Leonardo of Pisa (whose nickname was Fibonacci) in the early 13th century, although the sequence can be traced back to about 200 BCE in Indian literature. This sequence has produced a large amount of literature and has connections to many branches of mathematics.

In the Fibonacci sequence, each term is the sum of the two preceding terms. So if \(a_n\) is the \(n\)th term, we can write

\[ a_1 = a_2 = 1 \quad\text{and}\quad a_n = a_{n-1} + a_{n-2},\ \text{ for } n\geq 3. \]

This is an example of a second-order linear recurrence relation.

A first-order linear recurrence such as \(a_n = ka_{n-1}\), where \(k\) is a constant, is easily seen to have the solution \(a_n = a_1 \times k^{n-1}\), which is an exponential. By taking \(A = \dfrac{a_1}{k}\), we can write the solution as \(a_n = A\,k^n\).

One approach to solving a second-order linear recurrence is to guess an exponential solution of the form \(a_n = A\,k^n\), where \(A\) and \(k\) are non-zero constants. Substituting this into the recurrence for the Fibonacci sequence, we have

\[ A\,k^n = A\,k^{n-1} + A\,k^{n-2}. \]

Dividing by \(A\,k^{n-2}\), we see that \(k\) satisfies

\[ k^2 = k + 1, \]

which has solutions \(k = \dfrac{1}{2}(1 \pm \sqrt{5})\). Thus, we have found two exponential solutions

\[ a_n = A_1 \times \Biggl(\dfrac{1 + \sqrt{5}}{2}\Biggr)^n \qquad\text{and}\qquad a_n = A_2 \times \Biggl(\dfrac{1 - \sqrt{5}}{2}\Biggr)^n. \]

The theory of recurrence relations tells us that the general solution of this recurrence is obtained by summing these two solutions:

\[ a_n = A_1 \times \Biggl(\dfrac{1 + \sqrt{5}}{2}\Biggr)^n + A_2 \times \Biggl(\dfrac{1 - \sqrt{5}}{2}\Biggr)^n. \]

We can now use the initial condition \(a_1 = a_2 = 1\) to find that \(A_1 = \dfrac{1}{\sqrt{5}}\) and \(A_2 = -\dfrac{1}{\sqrt{5}}\). Finally, we have a formula for the \(n\)th Fibonacci number:

\[ a_n = \dfrac{1}{\sqrt{5}}\left(\Biggl(\dfrac{1+\sqrt{5}}{2}\Biggr)^n - \Biggl(\dfrac{1-\sqrt{5}}{2}\Biggr)^n\right). \]

Note that the number \(\dfrac{1}{2}(1 + \sqrt{5})\) that appears here is the golden ratio. One of many interesting facts about the Fibonacci sequence is that the only perfect squares in the sequence are 1 and 144.

Next page - History and applications - The Greeks