Mathematical induction used on Fibonacci Sequence

Question

I have no clue how to go about doing this question using induction. It states that the Fibonacci sequence is defined as:

F₀ = 0
F₁ = 1
F_n = F_n-2 + F_n-1 for n>=2

Let S(n) = F_o + F₁ + F₂ +...+ F_n. Prove that S(n)= F_n+2 -1

Answer 1

Let us prove that $$S(n)=\sum_{i=0}^{n}F_i=F_{n+2}-1$$ for all non-negative integers $n$ by induction.

For $n=0$, it holds trivially since $F_2=1$.

Assume that it holds for $n=k$, i.e. $$S(k)=\sum_{i=0}^{k}F_i=F_{k+2}-1.$$ Then, we have $$\begin{align}S(k+1)&=\sum_{i=0}^{k+1}F_i\\&=F_{k+1}+\sum_{i=0}^{k}F_k\\&=F_{k+1}+F_{k+2}-1\\&=F_{k+3}-1\\&=F_{(k+1)+2}-1.\end{align}$$

Hence, it holds for $n=k+1$.

Hence, $S(n)=\sum_{i=0}^{n}F_i=F_{n+2}-1$ for all non-negative integers $n$. Q.E.D.

Answer 2

Inductive step:

If $S(n)=F_0 + F_1 + \cdots + F_n=F_{n+2}-1$ then $S(n+1)=S(n)+F_{n+1}=F_{n+2} + F_{n+1} -1= F_{n+3}-1$