Proof By Induction Fibonacci Numbers

Question

How do I prove that

$$ f_{ 2n+1 } = 3f_{ 2n } + 1 - f_{ 2n-3 } $$

I'm not sure how to prove it using the defining recurrence of Fibonacci numbers.

Answer 1

Let's do this the most basic way:

$f_{2n+1} = 3f_{2n} + 1 - f_{2n-3}$

$f_{2n} + f_{2n-1} = 3f_{2n} + 1 - f_{2n-3}$

$f_{2n-1} = 2f_{2n} + 1 - f_{2n-3}$

$f_{2n-1} + f_{2n-3} = 2f_{2n} + 1$

$f_{2n-1} + f_{2n-3} = f_{2n} + f_{2n-1} + f_{2n-2} + 1$

$f_{2n-3} = f_{2n} + f_{2n-2} + 1$

$f_{2n-3} = f_{2n} + f_{2n-3} + f_{2n-4} + 1$

$0 = f_{2n} + f_{2n-4} + 1$

Right side is strictly positive, which shows that the first equation didn't hold at first.

Answer 2

As pointed out in Golob's answer, your equation is not in fact true. However we have $$\eqalign{f_{2n+1} &=f_{2n}+f_{2n-1}\cr &=(f_{2n-1}+f_{2n-2})+f_{2n-1}\cr &=2f_{2n-1}+(f_{2n-1}-f_{2n-3})\cr}$$ and therefore $$f_{2n+1}=3f_{2n-1}-f_{2n-3}\ .$$ Is there any possibility that this is what you meant?