Date: 01/29/2001 at 00:09:44 From: J Klein Subject: Fibonacci proof This Fibonacci proof is giving me major problems: F(2n)=(F(n))^2 + (F(n-1))^2 , I'm a biochem major, and not a math major, so I'm lost... help!?
Date: 01/29/2001 at 09:51:35 From: Doctor Rob Subject: Re: Fibonacci proof This is false, provided you are numbering the Fibonacci numbers so that F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, and so on. Proving something false will not prove to be an easy task. To see the falsity, notice that when n = 2, the right-hand side of your equation becomes F(2)^2 + F(1)^2 = 1^2 + 1^2 = 2 = F(3), whereas your equation would say that this equals F(4). That means that your proof must be of the following equation, instead: F(2*n-1) = F(n)^2 + F(n-1)^2. This one is true, and one proof goes like this. Let the roots of x^2 - x - 1 = 0 be a and b. The explicit expressions for a and b are a = (1+sqrt)/2, b = (1-sqrt)/2. In particular, a + b = 1, a - b = sqrt(5), and a*b = -1. Also a^2 = a + 1, b^2 = b + 1. Then the Binet Formula for the k-th Fibonacci number is F(k) = (a^k-b^k)/(a-b). Substitute this in the right-hand side of the identity you are trying to prove: F(n)^2 + F(n-1)^2 = (a^n-b^n)^2/(a-b)^2 + (a^(n-1)-b^(n-1))^2/(a-b)^2. Now put the right-hand side of this over the common denominator (a-b)^2, expand the numerator, and simplify using a*b = -1. That should give you F(n)^2 + F(n-1)^2 = (a^[2*n]+b^[2*n]+a^[2*n-2]+b^[2*n-2])/(a-b)^2. Now multiply each of the last terms in the numerator by -a*b = 1, factor out (a-b) from the numerator, and cancel it with a factor from the denominator, and recognize the Binet formula for F(2*n-1). Another proof would go like this: It is true for n = 1 and n = 2, by direct verification. Suppose it is true for all n <= k. Then F(2*k-3) = F(k-1)^2 + F(k-2)^2, F(2*k-1) = F(k)^2 + F(k-1)^2. Then F(2*k+1) = F(2*k) + F(2*k-1), by the Fibonacci recursion, = 2*F(2*k-1) + F(2*k-2), by the Fibonacci recursion, = 3*F(2*k-1) - F(2*k-3), by the Fibonacci recursion, = 3*[F(k)^2 + F(k-1)^2] - [F(k-1)^2 + F(k-2)^2], by the hypotheses above, = 3*F(k)^2 + 2*F(k-1)^2 - F(k-2)^2, = 3*F(k)^2 + 2*F(k-1)^2 - [F(k) - F(k-1)]^2, by the Fibonacci recursion, = 2*F(k)^2 + 2*F(k)*F(k-1) + F(k-1)^2, = 2*F(k)^2 + 2*F(k)*[F(k+1)-F(k)] + [F(k+1)-F(k)]^2, by the Fibonacci recursion, = F(k+1)^2 + F(k)^2. Applying the Principle of Mathematical Induction (strong form), we can conclude that the statement is true for every n >= 1. - 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.