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.
Great proof, thank you very much!
ReplyDeleteShouldn'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