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?
Best Answer
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}$$