# For the Fibonacci sequence prove that $\sum_{i=1}^n F_i= F_{n+2} - 1$

For the Fibonacci sequence $F_1=F_2=1$, $F_{n+2}=F_n+F_{n+1}$, prove that $$\sum_{i=1}^n F_i= F_{n+2} - 1$$ for $n\ge 1$.

I don't quite know how to approach this problem.

Can someone help and explain please?

-
Have you thought about 3-term recursion and proof by induction? Or you could write the iteration of the fibonacci seqence as a matrix vector product and solve (using diagonalization etc.) explicitly for $f_i$ and then show this explicitly – Nox Feb 18 '14 at 15:56
– Martin Sleziak Mar 3 '14 at 18:27
This post asks about combinatorial proofs of the same identity: math.stackexchange.com/questions/1145297/… – Martin Sleziak Feb 12 '15 at 19:23

Let us do an induction on $n$.

• Induction start. For $n=1$, we have $F_1=1=F_3-1$, so the induction start is done.

• Induction hypothesis. Let us assume we proved the assertion already for $n-1$.

• Induction step. Then

$$\sum_{k=1}^n F_k = \color{red}{\sum_{k=1}^{n-1} F_k} + F_n = \color{red}{F_{n+1}-1}+F_n = F_{n+2}-1$$

In the second equality we have used the induction hypothesis and in the last equality the definition of the Fibonacci sequence.

-

We define $F_{n + 2} = F_n + F_{n + 1}$. From this we see that

$$F_n = F_{n + 2} - F_{n + 1}\\ \sum_{i = 1}^nF_n = \sum_{i = 1}^n \left(F_{n + 2} - F_{n + 1}\right)\\ \sum_{i = 1}^nF_n = F_{n + 2} - F_2\\ \sum_{i = 1}^nF_n = F_{n + 2} - 1$$

We basically hinge upon the large amounts of cancellation that occurs on the right hand side when summing up from $i = 1$ to $n$.

-
please check your indices. – user127.0.0.1 Feb 18 '14 at 16:04
@user127.0.0.1 Thanks for pointing it out! edited. – Yiyuan Lee Feb 18 '14 at 16:05

Hint $\:$ It is straightforward to inductively prove this basic theorem on additive telescopy

$$\rm\ g(n)\ =\ \sum_{i\: =\: 1}^n\:\ f(i)\ \ \iff\ \ \ g(n) - g(n\!-\!1)\ =\ f(n)\ \ for\ \ n> 1,\,\ \ g(1)=f(1)$$

Your is special case $\rm\ f(n) = F_n,\ \ g(n) = F_{n+2}-1,\,$ which is easily checked to satisfy the above: simply notice that $\rm\,g(n)-g(n\!-\!1) = F_{n+2}-F_{n+1} = F_n = f(n),\$ and $\rm\ g(1) = f(1)$

The inductive proof of the general theorem is easier than that for your special case because the cancellation that occurs is much more obvious at this level of generality, whereas it is usually obfuscated by details of specific instances. Namely, the proof of the general theorem is just a rigorous inductive proof of the following telescopic cancellation

$$\rm \underbrace{\overbrace{g(1)}^{\large f(1)}\phantom{-g(1)}}_{\large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{-\,g(1)\!+\!\phantom{g(2)}}^{\large f(2)}\!\!\!\!\!\!\!\!\! \underbrace{g(2) -g(2)}_{\large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\phantom{-g(2)}+ g(3)}^{\large f(3)}\!\!\!\!\!\!\!\!\!\!\underbrace{\phantom{g(3)}-g(3)}_{\large =\ 0}\!+\:\cdots +\!g(n)\ =\ g(n)$$

This theorem reduces the inductive proof to simply verifying the RHS equalities, which is trivial polynomial arithmetic when $f(n),g(n)$ are polynomials in $n$. The above theorem is an example of telescopy, also known as the Fundamental Theorem of Difference Calculus, depending on context. You can find many more examples of telescopy and related results in other answers here.

-

Just for fun, let us try to prove $\sum\limits_{k=1}^n F_k= F_{n+2} - 1$ using Binet's formula.

Recall that we have $$F_n=\frac{a^n-b^n}{\sqrt5}$$ where $a=\frac{1+\sqrt5}2$ and $b=\frac{1-\sqrt5}2$.

A few identities, that are easy to check and which may be useful: \begin{align*} a+b&=1\\ a-b&=\sqrt5\\ ab&=-1\\ 1+a&=a^2\\ 1+b&=b^2 \end{align*} (Most of these identities simply follow from noticing that $a$, $b$ are roots of $x^2-x-1$ and using Vieta's formulas).

Now we want to compute $$\sum\limits_{k=1}^n F_k= \sum\limits_{k=1}^n \frac{a^k-b^k}{\sqrt5}= \frac 1{\sqrt5} \left(\sum\limits_{k=1}^n a^k- \sum\limits_{k=1}^n b^k\right)$$ Using the formula $1+x+\dots+x^n = \frac{x^{n+1}-1}{x-1}$ we get $$\begin{gather*} \frac1{\sqrt5} \left(\frac{a^{n+1}-1}{a-1}-\frac{b^{n+1}-1}{b-1}\right) = \\ \frac1{\sqrt5} \cdot \frac{(a^{n+1}-1)(b-1)-(b^{n+1}-1)(a-1)}{(a-1)(b-1)} = \\ \frac1{\sqrt5} \cdot \frac{a^{n+1}b-a^{n+1}-b-b^{n+1}a+b^{n+1}+a}{ab-a-b+1} = \\ \frac1{\sqrt5} \cdot \frac{-(a^{n+1}-b^{n+1})+ab(a^n-b^n)+(a-b)}{ab-(a+b)+1} = \\ \frac1{\sqrt5} \cdot \frac{-(a^{n+1}-b^{n+1})-(a^n-b^n)+\sqrt5}{-1-1+1} = \\ \frac{-(a^{n+1}-b^{n+1})-(a^n-b^n)+\sqrt5}{-\sqrt5}= \\ \frac{(a^{n+1}-b^{n+1})+(a^n-b^n)-\sqrt5}{\sqrt5}= \\ \frac{a^{n+1}-b^{n+1}}{\sqrt5}+\frac{a^{n}-b^{n}}{\sqrt5}-\frac{\sqrt5}{\sqrt5} = \\ F_{n+1}+F_n-1 = F_{n+2}-1 \end{gather*}$$

-