The Fibonacci numbers
are defined by a recurrence relation
This definition allows one to find any Fibonacci number, but for large values of it would be time-consuming to compute 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 , which enables one to calculate 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
Multiplying the equation by successive powers of , and simplifying at each step, gives
and so on.
A pattern is beginning to emerge. It appears that
The pattern can easily be established to be true for all natural numbers by Mathematical Induction.
It is clearly true when , and if we assume that it is true for some positive integer , i.e. that
showing that the formula is valid for the next number, .
Now go back to the original quadratic equation , which the standard quadratic formula shows has solutions
Substituting these two values into the equation gives
Since we want to find an expression for , the obvious thing to do now is subtract the two equations:
from which Binet’s Formula follows:
Originally by John Webb