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. 

2 comments:

  1. Great proof, thank you very much!

    ReplyDelete
  2. Shouldn't it be Fn+1 = (a^n + a^n-1 – b^n – b^n-1)/(a – b) at the commutative property step, not Fn+1 = (a^n + a^n-1 + b^n – b^n-1)/(a – b) ?

    ReplyDelete