# 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.

-
1=3-2, 1+2=5-2, 1+2+3=8-2, 1+2+3+5=13-2, etc. How are you getting F2=0? – anon Sep 2 '13 at 3:33
Since the sum index starts at $i=1$ you might want to start at $n=3$ rather than $2$. – L. F. Sep 2 '13 at 3:34
2-2 = 0..... but apparently I did something wrong. Can you please teach me how to do it? – Julio Garcia Sep 2 '13 at 3:35
If you plug in $n=2$ you get $\sum_{i=1}^0$ on the LHS. Notice something about that summation? There are no terms in it, so it's an empty sum which is zero. – anon Sep 2 '13 at 3:36
LF figured you wanted the summation to be non-empty, which requires the number up top the summation to be $\ge1$ (since the sum starts at $i=1$), and $n-2\ge1$ iff $n\ge3$. – anon Sep 2 '13 at 3:36

(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.

-

The sum of $F_i$ where $i$ is greater than equal to $1$ and less than or equal to $2-2=0$ is $0$--the so-called empty sum--which also happens to be $2$ less than $F_2=2,$ so it holds in the $n=2$ case. It does not hold for the $n=0,1$ cases, by the way. The lowest case for which it can be said to hold is $n=2$.

-
Ah, I see. Now that makes more sense. Had to think inside the left box this time :P Thanks, Cameron! – Julio Garcia Sep 2 '13 at 3:41