1
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Thanks! Makes sense, you're right, this is a better way to present it. $\endgroup$ – Omar N May 14 '15 at 4:29
  • $\begingroup$ 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) $\endgroup$ – Daniel May 14 '15 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.