# How to prove $\sum_{k=1}^{n}F_k = F_{n+2}-1$ by induction when $F_n$ is the Fibonacci sequence

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

• The main idea of your reasoning is right, however, you must clean a couple of things and add some details. – Daniel May 14 '15 at 4:03
• Gotcha, can you elaborate? – Omar N May 14 '15 at 4:04
• It's done, I've posted an answer. – Daniel May 14 '15 at 4:25

## 1 Answer

Here's a better way to present the induction step:

Assume statement is true for $n=i$,i.e.

$$\sum_{k=1}^{i}F_k = F_{i+2}-1$$

We want to prove that the statement is true for $n=i+1$, i.e.

$$\sum_{k=1}^{i+1}F_{k} = F_{((i+1)+2)}-1\ .$$

Indeed, this is the case since

\begin{align}\sum_{k=1}^{i+1}F_{k}=(F_1 + F_2 +\cdots+ F_i) + F_{i+1}& = (F_{i+2} - 1) + F_{i+1} \\ & =(F_{i+2}+ F_{i+1}) -1\\ \\ &=F_{i+3}-1 \end{align}

which is precisely what we wanted to prove.

• Thanks! Makes sense, you're right, this is a better way to present it. – Omar N May 14 '15 at 4:29
• In the sense that you should state explicitely what you want to prove! Don't write $\sum_{k=1}^{i+1}F_{k} = F_{((i+1)+2)}-1$ before you've proved it (unless you state that's what you want to prove) – Daniel May 14 '15 at 4:32