Do I need induction here?

Question

I am asked to prove, by using induction that

$$\sum\limits_{i=1}^n F(2i-1) = F(2n)$$

for all real numbers n where the function F(i) gives the i:th fibonacci number. The series stars off with $F(0) = 0, F(1) = 1$ etc

My question to you is, how, or rather why, I would need to use induction in this case?

Can it not simply be realized that the summation function equals

$$F(1) + F(3) + F(5) + F(7) + ... + F(2n-1)$$

and that $F(2n)$ can be simplifed as follows:

$$F(2n) = F(2n-1) + F(2n-2) = F(2n-1) + F(2n-3) + F(2n-4) = F(2n-1) + F(2n-3) + F(2n-5) + F(2n-6) ...$$

TLDR; tell me why I would need to use induction and why my "proof" is wrong.

Answer 1

As explained in the comments, your proof is not wrong, per se, and in fact, is effectively an outline of a proof by induction! An induction proof simply formalizes your heuristic idea.

The case $F(2)=F(1)$ is easy to check. And more generally, $$F\bigl(2(n+1)\bigr)=F\bigl(2(n+1)-1\bigr)+F\bigl(2(n+1)-2\bigr)=F\bigl(2(n+1)-1\bigr)+F(2n),$$ whence an inductive hypothesis gives you $$F\bigl(2(n+1)\bigr)=F\bigl(2(n+1)-1\bigr)+\sum_{i=1}^nF(2i-1)=\sum_{i=1}^{n+1}F(2i-1),$$ and you're done.

Answer 2

How about this?

$$\begin{align} &F(2n+2)\\ &=F(2n+1)+F(2n)\\ &=F(2n+1)+F(2n-1)+F(2n-2)\\ &=F(2n+1)+F(2n-1)+F(2n-3)+F(2n-4)\\ &=F(2n+1)+F(2n-1)+F(2n-3)+F(2n-5)+F(2n-6)\\ &=\cdots \end{align}$$

---

This is also possible.

$$\begin{align} &F(2n+1)\\ &=F(2n)+F(2n-1)\\ &=F(2n)+F(2n-2)+F(2n-3)\\ &=F(2n)+F(2n-2)+F(2n-4)+F(2n-5)\\ &=F(2n)+F(2n-2)+F(2n-4)+F(2n-6)+F(2n-7)\\ &=\cdots \end{align}$$

---

(By induction)

First, it holds for $n=1$. If it holds for $n$, $$F(2n+2)=F(2n+1)+F(2n)=F(2n+1)+\sum_{i=1}^{n}F(2i-1)=\sum_{i=1}^{n+1}F(2i-1)$$ Therefore it also holds for $n+1$.