Let $F_n$ be the Fibonacci sequence where $F_0$ = 0 , $F_1$ = 1 and $F_n$ = $F_{n-1}$ + $F_{n-2}$.
I want to prove the following by induction. $$\sum_{k=1}^{n}F_k = F_{n+2}-1$$
Here is what I have so far. Can anybody tell me if I am right?
Base case = n=1
$F_k$ = 1 = LHS
$F_{1+2}$ – 1 = 2 – 1 = 1 = RHS
Statement is true for n=1.
Assume statement is true for n=i.
$$\sum_{k=1}^{i}F_k = F_{i+2}-1$$
Prove statement is true for n=i+1.
$$\sum_{k=1}^{i+1}F_{k} = F_{((i+1)+2)}-1$$
$F_1$ + $F_2$ +…+ $F_i$ + $F_{i+1}$ = $F_{((i+1)+2)}-1$
$F_{i+2}$ – 1 + $F_{i+1}$ = $F_{((i+1)+2)}-1$
$F_{((i+1)+2)}-1$ = $F_{((i+1)+2)}-1$
Statement holds for n=i+1
Best Answer
Here's a better way to present the induction step: