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

F_{n+1} = F_{n} + F_{n1}

Original Formula

F_{n+1} = (a^n – b^n)/(a – b) + (a^n1 – b^n1)/(a – b)

Add like denominators

F_{n+1} = (a^n – b^n + a^n1 – b^n1)/(a – b)

Communative Property

F_{n+1} = (a^n + a^n1 + b^n – b^n1)/(a – b)

Distributive Property

F_{n+1} = (a^n1(a + 1) – b^n1(b + 1))/(a – b)

Substitute for a and b

F_{n+1} = (a^n1((1 + √(5))/2) + 2/2) – b^n1((1  √(5))/2 + 2/2))/(a – b)

Add like denominators

F_{n+1} = (a^n1((3 + √(5))/2) – b^n1((3 – √(5))/2))/(a – b)

Complicate Fractions

F_{n+1} = (a^n1((6 + 2√(5))/4) – b^n1((6 – 2√(5))/4))/(a – b)

Factor

F_{n+1} = (a^n1(((1 + √(5))/2)^2) – b^n1(((1 – √(5))/2)^2)/(a – b)

Substitution

F_{n+1} = (a^n1(a^2) – b^n1(b^2))/(a – b)

Add Exponents

F_{n+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^n1 – b^n – b^n1)/(a – b) at the commutative property step, not Fn+1 = (a^n + a^n1 + b^n – b^n1)/(a – b) ?
ReplyDelete