Fibonacci sequence induction question, $F_1+F_2+\ldots+F_{n-1}=F_{n+1}-1$

Question

The Fibonacci sequence is defined as the sequence where $F_1 = 1,F_2= 1$ and $F_i=F_{i-1}+ F_{i-2}$. Use induction to prove the that for $n\ge 2$, $$F_1+F_2+ \ldots+F_{n-1}=F_{n+1}-1$$

Answer 1

HINT

All proofs by induction look like this:

Base Case For the smallest value of $n$ (what is it in your case?), prove your statement (rephrase it plugging in the needed value of $n$ and use $F_1=1=F_1$ to show this is true.

Inductive Step

Assume the statement is true for all $n$ up to some $N-1$. Now use this to prove your statement for $n=N$. (Hint: what does your statement say for $n=N-1$ -- you are assuming it is true; can you prove your statement from that?)