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?