2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\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}.$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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