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?

Solution 1:

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.

Solution 2:

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$.

Solution 3:

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.

Solution 4:

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*} $$