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; F_n = (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.