Binet's Formula and Induction

Date: 11/28/2001 at 15:12:25
From: JT
Subject: Binet's Formula and Induction

Everywhere I look everyone keeps saying that Binet's formula can be 
solved by induction. But what is induction, and can you prove Binet's 
formula by induction?

Date: 11/28/2001 at 17:08:12
From: Doctor Rob
Subject: Re: Binet's Formula and Induction

Thanks for writing to Ask Dr. Math, JT.

The Principle of Mathematical Induction states that if a certain
statement that depends on n is true for n = 0, and if its truth for 
n = k implies its truth for n = k+1, then the statement is true for 
all integers n >= 0.

There is an equivalent form, which appears superficially to be
different. It states that if a certain statement that depends on n is 
true for n = 0, and if its truth for all n <= k implies its truth for 
n = k+1, then the statement is true for all integers n >= 0.

To apply this Principle in either form is to prove the statement "by 
induction."

Binet's formula is

   F(n) = (a^n-b^n)/(a-b).

Here F(n) is the nth Fibonacci number, defined by

   F(0) = 0,
   F(1) = 1,
   F(n) = F(n-1) + F(n-2), for all n >= 2.

The quantities a and b are defined by the formulas

   a = (1+sqrt[5])/2,
   b = (1-sqrt[5])/2 = -1/a.

They are the two roots of the quadratic equation x^2 - x - 1 = 0.
(Check this!)

To prove Binet's Formula, first show that it is true for n = 0 and
n = 1.  Then for any k >= 1, assume it is true for all n <= k (in
particular for n = k and n = k-1), so that

   F(k) = (a^k-b^k)/(a-b),
   F(k-1) = (a^[k-1]-b^[k-1])/(a-b).

Now add these two equations together. The left-hand side becomes 
F(k+1), according to the recursion defining the Fibonacci numbers.
Rearrange the right-hand side into the form

   F(k+1) = (a^k+a^[k-1]-b^k-b^[k-1])/(a-b),
          = (a^[k-1]*[a+1]-b^[k-1]*[b+1])/(a-b).

Now use the facts that a + 1 = a^2 and b + 1 = b^2, because a and b 
are the roots of x^2 - x - 1 = 0. Then the above expression will 
simplify into the form of Binet's Formula for n = k+1.

That establishes the hypotheses of the second form of the Principle of 
Mathematical Induction. The conclusion of the Principle must therefore 
hold, and Binet's Formula is true for all integers n >= 0.

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/