1
$\begingroup$

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.

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

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?

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.