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)/2, b = (1-sqrt)/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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.