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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.