5
$\begingroup$

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!

  • 0
    Are you using strong induction? Since you assumed the identity true for $n-1$ as well?2016-07-10

2 Answers 2

5

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}$

2

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.