# Prove that $F(1) + F(3) + F(5) + … + F(2n-1) = F(2n)$

(These are Fibonacci numbers; $f(1) = 0$, $f(3) = 1$, $f(5) = 5$, etc.) I'm having trouble proving this with induction, I know how to prove the base case and present the induction hypothesis but I'm unfamiliar with proving series such as this. Any help would be great. :)

• Why do you use two different notations for the numbers? Either $f(n)$ of $F(n)$. Then numbers are $0,1,1,2,3,5,\ldots$. So if $f(5)=5$ then $f(1)=1, f(3)=2$. – miracle173 Nov 24 '14 at 0:28

Assume this is true for $n$. Now, let's consider the sum:

$$F_1 + F_3 + \dots + F_{2n-1} + F_{2n+1}$$

By induction hypothesis, the sum without the last piece is equal to $F_{2n}$ and therefore it's all equal to:

$$F_{2n} + F_{2n+1}$$

And it's the definition of $F_{2n+2}$, so we proved that our induction hypothesis implies the equality:

$$F_1 + F_3 + \dots + F_{2n-1} + F_{2n+1} = F_{2n+2}$$

Which finishes the proof

• and you start with which $n$? For $n=1$ you get $0=f(1)=f(2)=?$ – miracle173 Nov 24 '14 at 0:52
• The question was about the induction step, so what I covered was the case $n>2$ – Jytug Nov 24 '14 at 16:44

Hint: If you can use the that the sequence of Fibonacci numbers is defined by the recurrence relation $$F(n)=F(n-1)+F(n-2)$$ then you can prove it by induction, since \begin{align*}F(2(n+1))&=F(2n+2)\\&=F(2n+1)+F(2n)\\&=F(2n+1)+\underbrace{F(2n-1)+\ldots+F(5)+F(3)+F(1)}_{=F(2n) \text{ by induction hypothesis}}\end{align*}

The following is formally not correct because it uses the "$\cdots$" symbol but it gives some insight. The proof can be formalized using induction. This was already done by @Jytug. $$\begin{eqnarray} F(1) + F(3) + F(5) + \cdots + F(2n-1)&= \\ 0+\left(F(1) + F(3) + F(5) + \cdots + F(2n-1)\right) &= \\ F(0)+\left(F(1) + F(3) + F(5) + \cdots + F(2n-1)\right)&=\\ \left(F(0)+F(1)\right) +\left( F(3) + F(5) + \cdots + F(2n-1)\right)&=\\ F(2)+\left( F(3) + F(5) + \cdots + F(2n-1)\right)&=\\ \left(F(2)+F(3)\right) + \left( F(5) + \cdots + F(2n-1)\right)&=\\ F(4) + \left( F(5) + \cdots + F(2n-1)\right)&=\\ \cdots&=\\ F(2n-2)+F(2n-1)&=\\ F(2n)& \end{eqnarray}$$

Since $F(2n)-F(2n-2)=F(2n-1)$, this reduces to a telescoping series: \begin{align} \sum_{k=1}^nF(2k-1) &=\sum_{k=1}^n(F(2k)-F(2k-2))\\ &=\sum_{k=1}^nF(2k)-\sum_{k=0}^{n-1}F(2k)\\ &=F(2n)-F(0)\\[9pt] &=F(2n) \end{align}

Here is a solution using Binet's formula:

$F(n) = a \alpha^n + b \beta^n$, for some $a,b \in \mathbb R$, and $\alpha,\beta$ the roots of $X^2=X+1$. (Their precise value is not really important here.)

Now, $\alpha^1 + \alpha^3 + \cdots + \alpha^{2n-1} =\alpha(1+\alpha^2 + \alpha^4 + \cdots + \alpha^{2n-2}) =\alpha\dfrac{\alpha^{2n}-1}{\alpha^2-1} =\alpha^{2n}-1$ because $\alpha=\alpha^2-1$.

Analogously, $\beta^1 + \beta ^3 + \cdots + \beta ^{2n-1} =\beta ^{2n}-1$.

Therefore, $F(1) + F(3) + F(5) + \cdots + F(2n-1) = a(\alpha^{2n}-1)+b(\beta ^{2n}-1)=F(2n)-a-b$.

Finally, $a+b=F(0)=0$.

• I usually prefer not to use Binet's formula if I can avoid it, just for elegance's sake. But this problem screamed for a solution with geometric series. – lhf Nov 24 '14 at 0:41