A Fibonacci and Lucas Number Relation

Date: 08/24/98 at 04:59:12
From: David Ng
Subject: How do I prove a Fibonacci vs Lucas relation?

Hi, 

This has been troubling me for quite some time now. How do I prove 
that:

   F(2n) = F(n) * L(n)

where F(x) is the xth Fibonacci number and L(y) is the yth Lucas 
number?

I have only reached this:

   F(2n) = (F(n+1))^2 - (F(n-1))^2

Date: 08/24/98 at 10:28:44
From: Doctor Floor
Subject: Re: How do I prove a Fibonacci vs Lucas relation?

Hi David,

Thank you for sending your question to Dr. Math.

To prove that F(2n) = F(n)L(n), I first like to use the explicit 
formulae for F(n) and L(n). To make these formulae I first introduce 
two very special members of the family of generalized Fibonacci 
sequences (i.e. sequences such that X(n) = X(n-1) + X(n-2) ). These 
special members are of the form:

   g = g^1, g^2, g^3, g^4, ...  [g nonzero]

In such a formula we must have that:

   g^n = g^(n-1) + g(n-2)
   g^n - g^(n-1) - g(n-2) = 0
   g^(n-2) * (g^2 - g - 1) = 0  
   g^2 - g - 1 = 0   [we can divide by g^(n-2) becuase g is nonzero]

So g must be one of the roots of g^2 - g - 1 = 0, so it must be one of 
the following numbers:

   P = (1+SQRT(5))/2  (a.k.a. the Golden Ratio)
   Q = (1-SQRT(5))/2

So we have two very special generalized Fibonacci sequences:

   P^1, P^2, P^3, P^4, ...
   Q^1, Q^2, Q^3, Q^4, ...

I leave it for you to check that, when you have two generalized 
Fibonacci sequences A(n) and B(n), and two numbers a and b, then 
a*A(n) + b*B(n) is a generalized Fibonacci sequence. In fact, all 
generalized Fibonacci sequences can be calculated in this way from 
P^n and Q^n.

I also leave it for you to check that (check the first two, the rest 
follows from being a generalized Fibonacci sequence):

   F(n) = (P^n - Q^n)/SQRT(5)
   L(n) = P^n + Q^n

Now that we know these formulae, we can conclude that:

   F(n) * L(n) = (P^n - Q^n)/SQRT(5) * (P^n + Q^n)
               = (P^n - Q^n)(P^n + Q^n)/SQRT(5)
               = ((P^n)^2 - (Q^n)^2)/SQRT(5)
               = (P^(2n) - Q^(2n))
               = F(2n)

as desired.

If you have a math question again, please send it to Dr. Math.

Best regards,

- Doctor Floor, The Math Forum
Check out our web site! http://mathforum.org/dr.math/   

Date: 08/24/98 at 10:42:58
From: Doctor Nick
Subject: Re: How do I prove a Fibonacci vs Lucas relation?

Hello David -

You've almost got it with your last statement.

Notice we can rewrite it as:

   F(2n) = (F(n+1) - F(n-1))(F(n+1) + F(n-1))

and since F(n+1) - F(n-1) = F(n), we have:

   F(2n) = F(n)(F(n+1) + F(n-1))

Now we use the fact that:

   L(n) = F(n-1) + F(n+1)

which you probably already know, or you can prove it with induction.  
This gives us:

   F(2n) = F(n)L(n) 

and that's it.

- Doctor Nick, The Math Forum
Check out our web site! http://mathforum.org/dr.math/