Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

up vote 2 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|improve this answer
add comment

Your Answer

 
discard

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.