Prove the Fibonacci Sequence by induction (Sigma F2i+1)=F2n

Question

Prove the following by using mathematical induction. The Fibonacci sequence is defined as a recursive equation: $F_{1}=1$;$F_{2}=1$; and $F_{k}$=$F_{k-1}$+$F_{k-2}$. For all n∈N, the Fibonacci relation holds $$\sum_{i=0}^{n-1} F_{2i+1} = F_{2n}$$ I have seen many variations of the fibonacci sequence but have not seen it in this form and am confused on how to solve it with induction. Any help would be greatly appreciated. I know you have to start with one, then k, then k+1.

Answer 1

OK, so just follow the basic proof schema for induction:

Base: show that the claim is true for $n=1$. This means that you need to show that $\sum_{i=0}^{1-1}F_{2i+1}=F_{2}$

Well, the LHS is just $F_1$, which is 1, and that indeed equals $F_2$

Step: Take some arbitrary number $k$. Assume it is true that $\sum_{i=0}^{k-1}F_{2i+1}=F_{2k}$

We now have to show that $\sum_{i=0}^{(k+1)-1}F_{2i+1}=F_{2(k+1)}$

Can you do that?