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.

  • $\begingroup$ 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? $\endgroup$ – anon Sep 2 '13 at 3:33
  • $\begingroup$ Since the sum index starts at $i=1$ you might want to start at $n=3$ rather than $2$. $\endgroup$ – L. F. Sep 2 '13 at 3:34
  • $\begingroup$ 2-2 = 0..... but apparently I did something wrong. Can you please teach me how to do it? $\endgroup$ – Julio Garcia Sep 2 '13 at 3:35
  • $\begingroup$ 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. $\endgroup$ – anon Sep 2 '13 at 3:36
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.