Proof on fibonacci numbers using recurrence relations

Question

I'm trying to prove the following just using the main recurrence relation for a fibonacci sequence: $$F_{2n+1} = 3F_{2n-1} - F_{2n-3}$$ I'm having some trouble, can someone provide a tip or place to start? I've broken all three terms into their recurrence relations but that doesn't get me very far.

Answer 1

Use the fact that $F_k = F_{k-1} + F_{k-2}$ multiple times: $F_{2n+1} = F_{2n} + F_{2n-1} = (F_{2n-1} + F_{2n-2}) + F_{2n-1} = 2F_{2n-1} + (F_{2n-1} - F_{2n-3}) = 3 F_{2n-1} - F_{2n-3}$

Answer 2

Hint: \begin{align*}3F_{2n-1}-F_{2n-3}&=3\left(F_{2n-2}+F_{2n-3}\right)-F_{2n-3}\\&=3F_{2n-2}+2F_{2n-3}\\&=2\left(F_{2n-2}+F_{2n-3}\right)+F_{2n-2}\\&=\cdots\end{align*}