Binet's formula for Fibonacci numbers
The Fibonacci numbers are well-known by the general public, due to their applications in many branches of science. If fn denotes the n-th Fibonacci number, these numbers are defined by the recurrence relation: fn+2=fn+1+fn, with the initial data or seeds f0=0 and f1=1. Hence the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,....
We would like to have a closed formula for fn, i.e. a formula which does not involve recurrence relations. The answer is given by the Binet's formula. It is named after the French mathematician Jacques Philippe Marie Binet (1786-1856) who published it in 1843, even though this formula was already known by Abraham de Moivre (1667-1754), Leonhard Euler (1707-1783) and Daniel Bernoulli (1700-1782).
The Binet's formula is
However there is a nicer way to express it, in terms of the the golden mean. Let Φ be the golden mean, also known as the golden ratio:
We recall that it is a root of the polynomial x2-x-1, this is the polynomial associated to the Fibonacci recurrence relation. Let φ be the other root of this polynomial, i.e.
The formula (1) in terms of Φ and φ is
In the following lines we will give a proof of this formula. Let Zn=aΦn+bφn, where a and b are constants.
We will show that Zn satisfies the same recurrence relation than the Fibonacci numbers, i.e. Zn=Zn-1+Zn-2, and find the values of a and b for which Z0=0 and Z1=1. Then the identity (2) follows.
Since Φ and φ satisfy the equation x2=x+1, for n a positive integer we have:
Hence
If we set Z0=0, then a+b=0. Similarly if Z1=1 then aΦ+bφ=1. So we have the system of equations:
Its solution is
Hence Zn=fn and the identity (2) holds.
References:
https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html
https://en.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet
T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001.
Nice explanation
I am glad that you liked it.