## Saturday, January 21, 2012

### Fibonacci Day: Proof of Binet's Formula

I don’t know if you noticed, but today’s a Fibonacci day! It is January 21, and 21 is the eighth Fibonacci number.

Several months back, I presented the explicit formula for Fibonacci numbers; Fn = (a^n –  b^n)/(a – b), assuming the following:

a = 1 + √(5)/2
b = 1 – √(5)/2

How on earth does that work? We’re going to use a technique called “proof by induction” to prove it. This is a difficult technique, but if you really try to follow each step, it will all come together in the end.

 Fibonacci Identity Fn+1 = Fn + Fn-1 Original Formula Fn+1 = (a^n – b^n)/(a – b) + (a^n-1 – b^n-1)/(a – b) Add like denominators Fn+1 = (a^n – b^n + a^n-1 – b^n-1)/(a – b) Communative Property Fn+1 = (a^n + a^n-1 + b^n – b^n-1)/(a – b) Distributive Property Fn+1 = (a^n-1(a + 1) – b^n-1(b + 1))/(a – b) Substitute for a and b Fn+1 = (a^n-1((1 + √(5))/2) + 2/2) – b^n-1((1 - √(5))/2 + 2/2))/(a – b) Add like denominators Fn+1 = (a^n-1((3 + √(5))/2) – b^n-1((3 – √(5))/2))/(a – b) Complicate Fractions Fn+1 = (a^n-1((6 + 2√(5))/4) – b^n-1((6 – 2√(5))/4))/(a – b) Factor Fn+1 = (a^n-1(((1 + √(5))/2)^2) – b^n-1(((1 – √(5))/2)^2)/(a – b) Substitution Fn+1 = (a^n-1(a^2) – b^n-1(b^2))/(a – b) Add Exponents Fn+1 = (a^n+1 – b^n+1)/(a – b)
Q.E.D

And there’s the proof. It is very confusing, but if you read it through a couple of times, it will begin to sink in. When I see proofs like this, it is massive chaos in the middle, but once it all comes together in the end, it just makes it such a cool proof.

1. 2. 