Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove the identity by induction: $$ F_{2n} = F_n L_n, $$ where $F_n$ and $L_n$ are the $n^{th}$ Fibonacci and Lucas number, respectively.

I have an answer but am not happy with it since it doesn't use induction. I resorted to using the identity $F_{2n} = F_{n + 1}^2 - F_{n - 1}^2$, which, admittedly, was not given to me in the text. I am, however, allowed to use the relations: $L_n = L_{n - 1} + L_{n - 2}$, $L_n = F_{n + 1} + F_{n - 1}$, and $F_{n + 1}^2 - F_n F_{n + 2} = (-1)^n$, since I proved them earlier.

So far I have shown the base cases of $n = 1, 2$, and have that $$ F_{n + 1} L_{n + 1} = F_n L_n + F_{n - 1} L_{n - 1} + F_{n - 1} L_n + F_n L_{n - 1} = F_{2n} + F_{2n - 2} + F_{n - 1} L_n + F_n L_{n - 1}, $$ so if I could show $F_{n - 1} L_n + F_n L_{n - 1} = 2 F_{2n - 1}$, then I would be done, but no such luck. I am trying to only use induction, no combinatorial arguments or other identities (such as Binet). Thank you in advance!

share|cite|improve this question
I know you said that you don't want the Binet formula, but it yields an extremely quick way to see why the result is true - $ \frac {\phi^{2n} - \phi^{-2n} } {2\sqrt{5}} = \frac {\phi^{n} - \phi^{-n}}{2 \sqrt{5} } \times ( \phi^{n} + \phi^{-n})$. It is also provides the motivation for finding related formulas, like the other one that N.S. gave in his solution. – Calvin Lin Dec 30 '12 at 0:57
Are you using strong induction? Since you assumed the identity true for $n-1$ as well? – Airdish Jul 10 at 4:03
up vote 4 down vote accepted

Try to prove induction both relations at once:

$$F_{2n} = F_n L_n \,,\mbox{and}, \, F_{n - 1} L_n + F_n L_{n - 1} = 2 F_{2n - 1}$$

share|cite|improve this answer

My guess is that you're working on exercise 15 of section 1-1 of George Andrew's Number Theory book. If so, that's exactly what I've done. All exercices of this section make only use of material exposed in the book, except this one, which is trickier. And indeed, I've tried hard to solve it by induction, without much success. So I look up on the internet, ending up on your question :) After some further search the formula (with any $m>1$) :

$F_{m+n} = F_{m+1}F_n + F_mF_{n-1}$

can actually be proven by induction (on $n$), use :

$F_{m+(n+1)} = F_{m+n} + F_{m + (n-1)}$

If you take $m=n$, then :

$F_{n+n} = F_{2n} = F_{n+1}F_n + F_nF_{n-1}=F_nL_n$

And voila, you've got your proof by induction :)

My guess is that George Andrew's goal was for us to prove the special case with $m=n$, without knowing that there's actually a more general formula. However that proof has no "obvious" relationship with Lucas numbers.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.