Induction proof fibonacci numbers

Question

I need to prove the following with induction:

n∑i=1 F(2i-1) = F(2n) for all n >= 1

I am stuck in my inductive step:

• n∑i=1 F(2i-1) = n∑i=1 F(2i-1) + F(2(n + 1) -1)

• = F(2n) + F(2(n + 1)-1)

• = F(2n) + F(2n + 1)

I am trying to get to F(2n + 2).

I know the following recursive definition of Fibonacci numbers: F(n) = F(n-1) + F(n-2), How can I use it to reach my answer?

Thanks a lot!

Answer 1

The statement seems to be $$ \sum_{i=1}^n F(2i-1)=F(2n),\qquad n\ge1 $$ The base case, $n=1$, is obvious because $F(1)=1$ and $F(2)=1$.

Assume it's the case for $n$; then $$ \sum_{i=1}^{n+1} F(2i-1)= \biggl(\,\sum_{i=1}^{n} F(2i-1)\biggr)+F(2(n+1)-1)= F(2n)+F(2n+1) $$ and the definition of the Fibonacci sequence gives the final step: $$ F(2n)+F(2n+1)=F(2n+2)=F(2(n+1)) $$

Answer 2

Sum up the recurrence relations: $$\sum_{i=1}^n F_{2i}=\sum_{i=1}^n F_{2i-1}+\sum_{i=1}^n F_{2i-2}=\sum_{i=1}^n F_{2i-1}+\sum_{i=0}^{n-1} F_{2i}$$ As $F_0=0$, this equality simplifies to: $$F_{2n}=\sum_{i=1}^n F_{2i-1}.$$