The Fibonacci numbers \(1, \ 1, \ 2,\ 3, \ 5,\ 8, 13,\ 21,\ 34, \ 55,\ 89,\ 144, \ \cdots\)

are defined by a recurrence relation

\[F_1 = F_2 = 1, \ F_{n+2} = F_{n+1} + F_n \ \textrm{ for } n \ge 1.\]

This definition allows one to find any Fibonacci number, but for large values of \(n\) it would be time-consuming to compute \(F_n\) this way. Worse, any error of calculating a term would be repeated and magnified in every subsequent term. So a natural question to ask is whether there is a simple formula, in terms of \(n\), which enables one to calculate \(F_n\) without having to find all the earlier Fibonacci numbers.

In 1843 the French mathematician Jacques Philippe Marie Binet announced that he had found a Fibonacci Formula. Although it was later revealed that other mathematicians, including Leonhard Euler and Abraham de Moivre, had worked out the same formula a hundred years earlier, the formula is today still labelled Binet’s Formula.

Deriving the Binet’s formula starts with a simple little quadratic equation \(x^2 = x + 1.\)

Multiplying the equation by successive powers of \(x\), and simplifying at each step, gives

\[x^3 = x(x^2) = x(x+1) = x^2 + x = (x+1) + x = 2x + 1\]

\[x^4 = x(x^3) = x(2x+1) = 2x^2 + x = 2(x+1) + x = 3x+2\]

\[x^5 = x(x^4) = x(3x+2) = 3x^2 + 2x = 3(x+1) + 2x = 5x + 3\]

\[x^6 = x(x^5) = x(5x+3) = 5x^2 + 3x = 5(x+1) + 3x = 8x + 5\]

and so on.

A pattern is beginning to emerge. It appears that \(x^n = F_n x + F_{n-1} \textrm{ for all } n \ge2.\)

The pattern can easily be established to be true for all natural numbers \(n\) by Mathematical Induction.

It is clearly true when \(n = 1\), and if we assume that it is true for some positive integer \(m\), i.e. that
\(x^m = F_mx + F_{m-1}\) then

\(x^{m+1} = F_{m}x^2 + F_{m-1}x = F_{m}(x+1) + F_{m-1}x = (F_{m} + F_{m-1})x + F_m = F_{m+1}x + F_m\),

showing that the formula is valid for the next number, \(m+1\).

Now go back to the original quadratic equation \(x^2 = x + 1\), which the standard quadratic formula shows has solutions

\(x = \dfrac {1\pm \sqrt 5}2\).

Substituting these two values into the equation \(x^n = F_nx + F_{n-1}\) gives

\[\Big(\dfrac{1+\sqrt 5}2 \Big)^n = F_n\Big(\dfrac{1+\sqrt 5}2\Big) + F_{n-1}\]

and

\[\Big(\dfrac{1-\sqrt 5}2 \Big)^n = F_n\Big(\dfrac{1-\sqrt 5}2\Big) + F_{n-1} \ .\]

Since we want to find an expression for \(F_n\), the obvious thing to do now is subtract the two equations:

\[\Big(\dfrac{1+\sqrt 5}2 \Big)^n - \Big(\dfrac{1-\sqrt 5}2 \Big)^n = F_n\Big(\dfrac{1+\sqrt 5}2 \ - \ \dfrac {1-\sqrt 5}2 \Big) = \sqrt5 F_n\]

from which Binet’s Formula follows:

\[F_n = \dfrac 1{\sqrt 5}\Big(\Big(\dfrac{1+\sqrt 5}2 \Big)^n - \Big(\dfrac{1-\sqrt 5}2 \Big)^n\Big) \ .\]

————

Originally by John Webb