# Induction proof fibonacci numbers

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!

• Um, you already have. F(2n + 2) by definition = F(2n + 1) + F(2N). – fleablood Oct 21 '15 at 22:00

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