Let $f_n$ denote the $nth$ Fibonacci number. Prove that


I am having trouble proving this. I thought to use induction as well as Binet's formula where,

$f_n=\frac{\tau^2-\sigma^2}{\sqrt5}$ where $\tau=\frac{1+\sqrt5}{2}$ and $\sigma=\frac{-1}{\tau}$.

Can someone give me a hand?


  • 1
    $\begingroup$ Perhaps it's easier in the form $$f_{2n+1} = f_{2n}+f_{2n-2}+\cdots+f_6+f_4+f_2+f_1$$ Just keep expanding the recurrence relation for the odd-indexed numbers! (Of course, this would formally map to an induction proof). $\endgroup$ – Henning Makholm Feb 22 '15 at 1:57

Using the recurrence relation for $f_n$ we find

\begin{align}f_2 + f_4 + \cdots + f_{2n} = (f_3 - f_1) + (f_5 - f_3) + \cdots + (f_{2n+1} - f_{2n-1}), \end{align}

which telescopes to $f_{2n+1} - f_1 = f_{2n+1} - 1$.


This can be proven with induction. If we're saying the sequence starts $1,1,2,\ldots$ then clearly $f_2 = f_3 - 1$.

Now assume $f_2\:+\:f_4\:+\ldots+f_{2n}=f_{2n+1}-1$. Add $f_{2n+2}$ to both sides. Then

$$f_2\:+\:f_4\:+...+f_{2n} + f_{2n+2}= f_{2n+2}+f_{2n+1}-1$$

And since $f_{2n+2}+f_{2n+1} = f_{2n+3}$, the result follows.


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.