I am trying to prove by induction the following proposition of the fibonacci sequence:
The fibonacci sequence is defined recursively as: $f_1 = 1$, $f_2 = 1$, and that for all integers $k>=1$, $f_{k+1} = f_{k+1} +f_k $
Propostion I am trying to prove:
$\sum_{i=1}^{k} F_{2i}=F_{2k+1}-1$ for all $k∈N$
So far I have this:
Base case:
For $F_1$: $\sum_{i=1}^{k} F_{2i}$ = $F_{2(1)}$ = $F_{2}$ This is true.
Induction Hypothesis:
$\sum_{i=1}^{n+1} F_{2i}$ = $F_{2(n+1)}$
I am not sure if what I have so far is correct.
I have brainstormed this also:
That $f_2 = f_3 - 1$. And that $f_2\:+\:f_4\:+\ldots+f_{2n}=f_{2n+1}-1$. By adding $f_{2n+2}$ to both sides, you get $f_2\:+\:f_4\:+...+f_{2n} + f_{2n+2}= f_{2n+2}+f_{2n+1}-1$. And $f_{2n+2}+f_{2n+1} = f_{2n+3}$.
I am not sure how to prove the proposition by induction properly. I have a general understanding of how induction works and why the proposition is true, but I am having trouble proving it with induction steps. I think I need to somehow get to $f_{2n} = f_{2(n+1)+1}-1$, but I am struggling with that. I haven't practiced much strong induction yet, so I am only looking for a simple proof. To provide context as to why I am doing this exercise: I am planning to use this proof as a base for me to refer back to when doing more complex proofs that also involve the fibonacci sequence.
Thank you for all the help or any proofs provided.
We want to prove $\varphi(n)$ for all $n\ge1$, with $\varphi(n)$ meaning $\sum_{i=1}^nF_{2i}=F_{2n+1}-1$. The principle of mathematical induction states that if $\varphi(1)$ (base case) and $\forall k\ge1(\varphi(k)\to\varphi(k+1))$ (induction step), $\forall n\ge1(\varphi(n))$. Your calculations have proved the base case $F_2=F_3-1$ and the induction step viz.$$\sum_{i=1}^kF_{2i}=F_{2k+1}-1\implies\sum_{i=1}^{k+1}F_{2i}=\sum_{i=1}^kF_{2i}+F_{2k+2}=F_{2k+1}-1+F_{2k+2}=F_{2k+3}-1,$$so you're done.
(The principle is usually stated as starting at $0$; $\varphi(0)$ equates an empty sum, i.e. $0$, to $F_1-1$, so we could have taken an $n=0$ base step. But based on your calculations I started at $n=1$, which is a common definition of $\Bbb N$.)