# Proof By Induction Fibonacci Numbers

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.

• yep wasn't sure how to use the superscript, sorry – gexcen Nov 14 '14 at 1:02

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?

• yes thanks. I needed the direct equation – gexcen Nov 14 '14 at 1:30

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.

• Thx, this was very helpful :) – gexcen Nov 14 '14 at 1:33