fibonacci-numbersinductionsummation
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.
This identity is clear from the following diagram:
(imagine here a generalized picture with $F_i$ notation)
The area of the rectangle is obviously
$$F_n(F_{n}+F_{n-1})=F_nF_{n+1}$$
On the other hand, since the area of a square is x^2, it is obviously:
$$F_1^2+F_2^2+\dots+F_n^2$$
Therefore:
$$F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$$
You can even convert this graphical proof to an inductive proof - your inductive step would consist of adding a square $F_{n+1} * F_{n+1}$.
From the start, there isn't a clear statement to induct on. As such, you have to guess the induction hypothesis, and find an explicit pattern which you could describe.
Hint: Look at the sequence of values of $\frac{f_{2k}}{f_k}$. Do you see a pattern there? That suggests to prove the following fact:
$$ \frac{f_{2k+2}} { f_{k+1} } = \frac{f_{2k} } { f_k } + \frac{f_{2k-2} } {f_{k-1} } $$
Check that the first two terms of this series $g_n = \frac{f_{2n}}{f_n}$ are integers, hence conclude by induction that every term is an integer.
Best 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.