summation - Fibonacci using proof by induction: $sum_{i=1}^{n-2}F_i=F_n-2$

everyone.

I have been assigned an induction problem which requires me to use induction with the Fibonacci sequence. The summation states:

$$\sum_{i=1}^{n-2}F_i=F_n-2\;,$$ with $F_0=F_1=1$.

I have tried going through the second one to see if it was right, but I came with a weird thing. $F_2$ should be $2$, but according to this statement, it equals zero.

What am I doing wrong? It got my attention.

Thank you for your time.

Answer

(First an aside: the Fibonacci sequence is usually indexed so that $F_0=0$ and $F_1=1$, and your $F_0$ and $F_1$ are therefore usually $F_1$ and $F_2$.)

The recurrence might be more easily understood if you substituted $m=n-2$, so that $n=m+2$, and wrote it

$$\sum_{i=1}^mF_i=F_{m+2}-2\;.\tag{1}$$

Now see what happens if you substitute $m=1$: you get $F_1=F_{1+2}-2$, which is correct: $F_1=1=3-2=F_3-2$. You can try other positive values of $m$, and you’ll get equally good results. Now recall that $m=n-2$: when I set $m=1,2,3,\dots$, I’m in effect setting $n=3,4,5,\dots$ in the original formula. That’s why one commenter suggested that you might want to start $n$ at $3$.

What if you try $m=0$? Then $(1)$ becomes $$\sum_{i=1}^0F_i=F_2-2=2-2=0\;,$$ but as Cameron and others have pointed out, this is exactly what should happen: $\sum_{i=a}^bx_i$ can be understood as the sum of all $x_i$ such that $a\le i\le b$, so here we have the sum of all $F_i$ such that $1\le i\le 0$. There are no such $F_i$, so the sum is by convention $0$.

The induction argument itself is pretty straightforward, but by all means leave a comment if you’d like me to say something about it.