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

 How clear is this post?