Hey guys I have just started looking into induction and came across this problem regarding fibonnaci sequence that I don't quite know how to solve.
The fibonacci sequence $\{f_n\}$ is defined by $f_0 = 0, f_1 = 1, f_n = f_{n−1} + f_{n−2}$ for all $n \ge 2$. The first few terms of the fibonacci sequence are $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597...$$
Prove that for all $n \in \mathbb N$, $$f_{2n} = \sum_{i = 1}^n f_{2i - 1}$$
For the Base Case I got that $f_{2n} = f_2 = 1$ and that $f_{2-1} = 1$.
Inductive Hypothesis: $f_{2(k)} = \sum_{i = 1}^{k} f_{2i - 1}$.
I am unsure how to solve for the inductive conclusion. If anyone could help me understand a solution that would be greatly helpful! Thanks!
Your induction hypothesis isn't correct; you should assume that the result is true for the case $k$, and use it to establish the case $k + 1$. Use the definition of the Fibonacci numbers directly:
\begin{align*} f_{2(k + 1)} &= f_{2k + 2} \\ &= f_{2k + 1} + f_{2k} \\ &= f_{2k + 1} + \sum_{i = 1}^k f_{2i - 1} \quad \text{(induction hypothesis)} \\ &= \sum_{i = 1}^{k + 1} f_{2i - 1} \end{align*}
Can you justify every step, and see how this proves the claim?