Proving property of Fibonacci Numbers using Binet's Formula?

Question

Let α and β be the roots of x² - x - 1 = 0 (the Golden ratio and it's complement).  Then Binet's formula states that
F_n = (αⁿ - βⁿ) / (α - β)

where F_n is the nth Fibonacci Number.

Now, what I want to know is there any way besides just some crazy algebraic trick to prove that
F_{n+m} = F_{m+1}F_n + F_mF_{n - 1}

using Binet's Formula.  I can do it through induction quite easily, but the instructions state that Binet's Formula is to be used, and even that with induction is just messy... unless I'm missing something.

I know
aⁿ - bⁿ = (a - b)∑{i = 1,n} a^(n - i) b^(i - 1)

but that doesn't seem to be of much help.


Any assistance is greatly appreciated.

Eugene · Accepted Answer

Well, this is what I have.  I won't be using induction.

If it can be shown that

(a^(n+m) - b^(n+m))(a - b) = (a^(m+1) - b^(m+1))(a^n - b^n) + (a^m - b^m)(a^(n-1) - b^(n-1)) (*)

for all m and n, then the result follows by dividing through by (a - b)^2.  To verify (*), expand the right-hand side to get

a^(m+n+1) + b^(n+m+1) - a^(m+1)b^n - b^(m+1)a^n + a^(m+n-1) + b^(m+n-1) - a^m b^(n-1) - b^m a^(n-1).

Regroup the terms as

a^(m+n+1) + b^(n+m+1) - (b^(m+1)a^n + a^m b^(n-1)) - (a^(m+1)b^n + b^m a^(n-1)) + a^(m+n-1) + b^(m+n-1).

Since ab = -1,

b^(m+1)a^n + a^m b^(n-1) = a^m b^(n-1) (ab + 1) = 0 and

a^(m+1)b^n + b^m a^(n-1) = b^m a^(n-1) (ab + 1) = 0.

So the resulting expression is

a^(m+n+1) + b^(n+m+1) + a^(m+n-1) + b^(m+n-1).

Since ab = 1, a = -1/b and b = -1/a.  Thus a^(m+n-1) = -a^(m+1)b and b^(m+n-1) = -b^(m+1)a, yielding

a^(m+n+1) + b^(n+m+1) - a^(m+n)b - b^(m+n)a

= (a^(n+m) - b^(n+m))(a - b).

? · Answer

http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

Trending News

Proving property of Fibonacci Numbers using Binet's Formula?

2 Answers