How do I add summation formula's like this: $F(n+2) = 1 + \sum\limits_{i=0}^{n} F(i)$?

Question

I have a Fibonacci problem ... basically I have to show that:

$$F(n+2) = 1 + \sum_{i=0}^{n} F(i)$$

Using strong induction, I must now show that:

$$F(n+2) = F(n+1) + F(n)$$ $$F(n+2) = (1 + \sum_{i=0}^{n-1} F(i)) + (1 + \sum_{i=0}^{n-2} F(i))$$ $$F(n+2) = 2 + \sum_{i=0}^{n-1} F(i) + \sum_{i=0}^{n-2} F(i)$$

---

How do I add these two summations to show that they equal the first equation (at the top)?

Please provide the steps with explanation as to what you are doing. Thanks

Answer 1

You’re making it much harder than it really is. In particular, you don’t need strong induction. Your induction hypothesis is that

$$F(n+2)=1+\sum_{k=0}^nF(k)\;.$$

Now add $F(n+1)$ to both sides and simplify each side:

$$F(n+3)=F(n+2)+F(n+1)=1+\sum_{k=0}^nF(k)+F(n+1)=1+\sum_{k=0}^{n+1}F(k)\;.$$

The equality of the leftmost and rightmost quantities in that string is exactly what you needed to prove for your induction step.

Answer 2

If you are asking for any induction proof for this identity, then your question is a duplicate of some already existing questions, for example, Fibonacci using proof by induction: $\sum_{i=1}^{n-2}F_i=F_n-2$ (and other posts linked there) or For the Fibonacci sequence prove that $\sum_{i=1}^n F_i= F_{n+2} - 1$ (and other posts linked there

If you are asking specifically whether the approach you've chosen can be somehow finished, the answer is that it is possible.

From the result you are trying to prove it seems that you are using $F(0)=0$ and $F(1)=1$. (You should probably specify this in your question, since $F(0)=F(1)=1$ is quite common too.)

---

You have \begin{align*} F(n+2) &\overset{(1)}= 2 + \sum_{i=0}^{n-1} F(i) + \sum_{i=0}^{n-2} F(i)\\ &\overset{(2)}= 2 + \sum_{i=1}^{n} F(i-1) + \sum_{i=2}^{n} F(i-2)\\ &\overset{(3)}= 1+ F(-1) +\sum_{i=1}^{n} F(i-1) + F(-2)+ F(-1) +\sum_{i=2}^{n} F(i-2)\\ &\overset{(4)}= 1 + \sum_{i=0}^{n} F(i-1) + \sum_{i=0}^{n} F(i-2)\\ &\overset{(5)}= 1 + \sum_{i=0}^{n} (F(i-1) + F(i-2))\\ &\overset{(6)}= 1 + \sum_{i=0}^{n} F(i) \end{align*}

Notice that if you are using $F(0)=F(1)=1$ (as you mentioned in a comment under this answer - now deleted), then you get $F(-1)=F(1)-F(0)=0$ and similarly $F(-2)=F(0)-F(-1)=1$.

I will add that that the same approach would work with $F(0)=0$ and $F(1)=1$, which is probably more usual. (This are the initial values mentioned in the Wikipedia article about Fibonacci numbers.) In this case we would get $F(-2)=-1$, $F(-1)=1$ and again $2=1+F(-1)+F(-2)+F(-1)$. With these initial values we have $F(-n)=(-1)^{n+1}F(n).)

$(3)$: Here we simply used $2=1+F(-1)=1+F(-1)+F(-2)+F(-1)$. (Which is true since $F(-1)=0$ and $F(-2)=1$.) We are doing this because these are precisely the numbers missing in the sums to get a sum from $0$ to $n$.

---

After posting this answer I found a rather similar approach in this answer: Fibonacci proof question $\sum_{i=1}^nF_i = F_{n+2} - 1$. You might have a look at the way it is written there to see whether it could make things clearer.