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. :)
 A: 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
A: 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*}$$
A: 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}
$$
A: 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$.
A: 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}
$$
