5
$\begingroup$

(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. :)

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – miracle173 Nov 24 '14 at 0:28
4
$\begingroup$

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

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

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*}$$

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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} $$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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} $$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lhf Nov 24 '14 at 0:41

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.