Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
show 3 more comments

2 Answers

up vote 0 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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