# Sum of Fibonacci numbers

While trying to find find a formula to calculate the length of the golden spiral I came across the sum of the Fibonacci numbers. I noticed that $$\text{Fibonacci numbers: }1,1,2,3,5,8,13,21,34...$$ $$1+1+2= 5-1$$ $$1+1+2+3= 8-1$$ and that $$2+3+5+= 13-2$$ $$3+5+8=21-5$$ so generalized that writing: $$\sum^n_{i=k} F_i=F_{n+2}-F_{i+1}$$ where $F_n$ is the nth Fibonacci number. But the sentence "I noticed that" is not a sufficient demonstration; I tried a lot but I couldn't find a correct demonstration.

How can I find it?

• Have you tried using induction? It seems like it should be pretty straightforward. – pjs36 Mar 29 '15 at 19:56
• That should follow easily from math.stackexchange.com/questions/243606/…. – Martin R Mar 29 '15 at 19:57
• @pjs36 The index of the summation is $k$? Because I don't understand the $F_{i+1}$ on RHS. – Marco Cantarini Mar 29 '15 at 20:15
• This is probably in the book Fibonacci and Lucas Numbers with Applications with a short proof. – Robert Soupe Mar 30 '15 at 0:30

Fibonacci numbers can be written as a matrix using:

$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1}\end{bmatrix}$$

So that any sum, using $X= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$, is :

$$\sum_{k=a}^b F_n = \left( \sum_{k=a}^b X^n \right)_{2,1}$$

which is a geometric sum. So you can use geometric sum formula:

\begin{align} \sum_{k=a}^b X^n &= \sum_{k=0}^b X^n - \sum_{k=0}^{a-1} X^n \\ &= (X^{b+1} - I)(X-I)^{-1}- (X^{a} - I)(X - I)^{-1} \\ &= \left(X^{b+1} - X^{a}\right)(X - I)^{-1} \\ \end{align}

Now $(X - I)^{-1} = X$ for this particular matrix (property of Fibonacci recursion):

\begin{align} \sum_{k=a}^b X^n &= \left(X^{b+1} - X^{a}\right)X \\ &= \left(X^{b+2} - X^{a+1}\right) \\ \end{align}

$$\sum_{k=a}^b F_n = F_{b+2} - F_{a+1}$$

Using $$\sum_{i=0}^{n}F_{i}=F_{n+2}-1$$ (you can find a proof here) and assuming $k<n$, then $$\sum_{i=k}^{n}F_{i}=\sum_{i=0}^{n}F_{i}-\sum_{i=0}^{k-1}F_{i}=F_{n+2}-F_{k+1}.$$