Fibonacci Proof

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[5])/2,
   b = (1-sqrt[5])/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/