Fibonacci Trick

Date: 06/01/99 at 18:16:10
From: Stephanie Roberts
Subject: Fibonacci Sequence

I am interested in why the Fibonacci trick works. How do f(n-1), 
f(n+1), and f(n)^2 relate to each other? I am not a good math student 
at all but the Fibonacci sequence has really interested me. I have 
been working for a while on a way to solve this but I haven't gotten 
anywhere. Please help me! I would like to look at why this works and 
see if it helps to understand the ways the Fibonacci sequence shows up 
in nature, etc.

Thank you so much.
Stephanie

Date: 06/01/99 at 18:46:55
From: Doctor Anthony
Subject: Re: Fibonacci Trick

For the Fibonacci sequence show:

     [F(n+1) * F(n-1)] - [F(n)]^2 = (-1)^n


The expression for the nth term of the Fibonacci sequence is:

               1      [1+sqrt(5)]^n        1      [1-sqrt(5)]^n
     F(n) = ------- * -------------  -  ------- * -------------
            sqrt(5)        2^n          sqrt(5)        2^n

I will write this in the form

               1
     F(n) = ------- * [P^n - Q^n]
            sqrt(5)  

           1+sqrt(5)                 1-sqrt(5)
where  P = ---------     and     Q = ---------
               2                         2

Note that  P+Q = 1
           P-Q = sqrt(5)
            PQ = 1/4 - 5/4 = -1


We are asked to show that  [F(n+1) * F(n-1)] - [F(n)]^2 = (-1)^n


   [F(n)]^2 = (1/5)*[P^n - Q^n]^2

            = (1/5)*[P^(2n) + Q^(2n) - 2*P^n*Q^n]    ..............(1)


   F(n+1) * F(n-1) = (1/5)*[P^(n+1) - Q^(n+1)]*[P^(n-1) - Q^(n-1)]

                   = (1/5)*[P^(2n) + Q^(2n) - P^(n+1)*Q^(n-1)
                      - P(n-1)*Q^(n+1)]              ..............(2)


subtracting (1) from (2) we get:

     (1/5)*[-P^(n+1)*Q^(n-1) - P^(n-1)*Q^(n+1) + 2*P^n*Q^n]

   = (1/5)*[-P^(n-1)*Q^(n-1)*(P^2 + Q^2) + 2*P^n*Q^n]

   = (1/5)*P^(n-1)*Q^(n-1)*[-(P^2 + Q^2) + 2*P*Q]

   = -(1/5)*P^(n-1)*Q^(n-1)*[P^2 - 2*P*Q + Q^2]

   = -(1/5)*P^(n-1)*Q^(n-1)*(P-Q)^2


but (P-Q)^2 = 5, so we obtain

   = -P^(n-1)*Q^(n-1)

   = -(PQ)^(n-1)


but PQ = -1 and so the difference between (1) and (2) reduces to:

   = -(-1)^(n-1)

   = (-1)^n

and this completes the proof.

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