Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 15:56
    

4 Answers 4

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.

share|improve this answer

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

share|improve this answer
    
please check your indices. –  user127.0.0.1 Feb 18 at 16:04
    
@user127.0.0.1 Thanks for pointing it out! edited. –  Yiyuan Lee Feb 18 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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