Trying to prove $\sum_{i=1}^{N-2} F_i = F_N -2$

Question

I'm trying to prove that $\sum_{i=1}^{N-2} F_i = F_N -2$. I was able to show the base case for when $N=3$ that it was true.

Then for the inductive step I did:

Assume $\sum_{i=1}^{N-2} F_i = F_N -2$ is true for $3 \leq k \leq N$. Prove $\sum_{i=1}^{(k+1)-2} F_i = F_{k+1}-2$.

$LHS = \sum_{i=1}^{(k+1)-2} F_i = \sum_{i=1}^{k-1} F_i = ?$

I'm not sure how to simplify from there. I don't want just a straight answer. I want to know why that is the next step. Thanks for any help.

UPDATE:

Aaron wrote an answer and said that $\sum_{i=1}^{n+1} a_i = \sum_{i=1}^{n} a_i + a_{n+1} = b_n + a_{n+1}$. I've seen this response in other posts but I don't understand the part that says $\sum_{i=1}^n a_i + a_{n+1}$. My reasoning is that if $n = 4$ then the sum would be (using the fibonacci numbers): $(1 + 8) + (2 + 8) + (3+8) + (5+8) = 9+10+11+12 = 33$. I'm just following the pattern of $a_i + a_{n+1}$ and then summing them all up from index $i= 1$ to $n$. This answer (33) does not seem right especially since $\sum_{i=1}^{n+1} a_i$ equals to the sum I just calculated. But when I calculate $\sum_{i=1}^{n+1} a_i$, I get $(1 + 2 + 3 +5) = 11$ when $n=3$ (to get a total up to 4). I hope this is clear. Anyways, this is my reasoning. So where am I going wrong?

Answer 1

Why questions are always a little difficult to answer, especially for problems that can be attacked multiple ways. For this particular problem, and more generally, for problems of the form $\sum_{i=1}^n a_i = b_n$, if you proceed by induction, you can write $\sum_{i=1}^{n+1} a_i = \sum_{i=1}^{n} a_i + a_{n+1} = b_n + a_{n+1}$ by your induction hypothesis. This allows you to reduce your problem (whatever it is) to showing $b_{n+1}=b_n+a_{n+1}$. So the "why" is answered by "because induction reduces a problem about a sum of $n$ terms into a problem about a sum of $2$ terms."

But induction isn't always used in this way, and so the heuristic of "plus in $n+1$ for $k$, compare the result to plugging in $n$ for $k$, apply the induction hypothesis to simplify, and massage until the answer appears" doesn't always work. It works often enough, though, that when you notice a pattern and you want to try to prove it by induction, that is a good way to pull it off.

Answer 2

$\displaystyle \sum_{n=1}^{(N+1)-2}F_n = F_N-2 + F_{N-1}=F_{N+1}-2$, and you're done.

Answer 3

Here's an alternative method using generating functions. First we consider a $f(x)=\sum_n a_nx^n$. Clearly

$\frac{f(x)}{1-x}=\sum_n x^n \sum_na_n x^n=\sum_n \left(\sum_{k=0}^n a_n\right)x^n.$

And so $f(x)/(1-x)=a_0+(a_0+a_1)x+...$. Thus $f/(1-x)$ is the generating function for the sequence $\left \{\sum_{j=0}^na_n\right\}_{n\geq 0}$. So then $F/(1-x)$ is the generating function for $\sum_k F_k$. Furthermore, a very similar argument shows that $F_{n+2}-1=(F-x)/x^2-1/(1-x)$. Using the fact that $F(x)=x/(1-x-x^2)$, we can use simple algebra to show that $\frac{F}{1-x}=\frac{F-x}{x^2}-\frac{1}{1-x}$.