Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Logic
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/