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?
$\endgroup$ 42 Answers
$\begingroup$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}$$
$\endgroup$ $\begingroup$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}.$$
$\endgroup$
