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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following: $$\begin{align} F_{n-1}+F_{n-2}&=F_n\\ F_{n-1}+F_{n-2}+F_{n-3}&=F_{n-1}+F_{n-1}\\ &=2F_{n-1}\\ F_{n-1}+F_{n-2}+F_{n-3}+F_{n-4}&=F_n+F_{n-2}\\ &=L_{n-1}\\ F_{n-1}+F_{n-2}+F_{n-3}+F_{n-4}+F_{n-5}&=F_{n-1}+L_{n-2}\\ &=F_{n-1}+F_{n-1}+F_{n-3}\\ &=2F_{n-1}+F_{n-3}\\ F_{n-1}+F_{n-2}+F_{n-3}+F_{n-4}+F_{n-5}+F_{n-6}&=2(F_{n-1}+F_{n-4}) \end{align}$$ Is there some logic to this pattern? Can it be predicted? Is there a formula that can be used to compute the value of $$\sum_{i=1}^{r}{F_{n-i}}$$ in terms of only Fibonacci and Lucas numbers or their multiples, no constant terms, without resorting to a summation?

share|cite|improve this question
Big hint: if $\mathcal{F}_n = \sum_{i=1}^nF_i$, then your sum is $\mathcal{F}_{n-1}-\mathcal{F}_{n-r+1}$. Now, you should be able to find a formula for $\mathcal{F}_n$... – Steven Stadnicki Apr 22 '14 at 22:38
Sorry, @StevenStadnicki, this is NOT a homework question. Feel free to give an answer. – Brian J. Fink Apr 22 '14 at 22:42
How do you get $F_{n-1}+F_{n-2}+F_{n-3}+F_{n-4}+F_{n-5}=2F_n$? – draks ... Apr 22 '14 at 22:49
@BrianJ.Fink I didn't figure it was homework! But it's also pretty easy and (IMHO) pretty fun to figure out for yourself. – Steven Stadnicki Apr 22 '14 at 22:53
@Steve I guess the constant will cancel out in that case. – Brian J. Fink Apr 22 '14 at 22:55

$$F_n = \left(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n\right)_{2,1}$$

which let's us treat it like any other summation except using matrices instead of scalar numbers, just remember that matrix multiplication doesn't commute and everything else is the same.

Using $X = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ and $I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$, proceed:

$$\begin{align} S &= \sum_{i=1}^r F_{n - i} \\ &= \left(\sum_{i=1}^r X^{n-i}\right)_{2,1}\\ &= \left(\sum_{i=n - r}^{n - 1} X^i\right)_{2,1} \\ &= \left(X^{n - r} \underbrace{\sum_{i=0}^{r - 1} X^i} _\text{Q = Geometric Series} \right)_{2,1}\\ \end{align}$$

Geometric series,

$$\begin{align} Q &= \sum_{i=0}^{r - 1} X^i\\ &= \left(X^{r} - I\right) \left(X - I\right)^{-1}\\ &= \left(X^{r} - I\right) X\\ &= X^{r+1} - X \end{align}$$

$$\begin{align} S &= \left(X^{n - r}\right) \left(X^{r+1} - X\right)_{2,1}\\ &= \left(X^{n+1} - X^{n+1-r}\right)_{2,1}\\ &= F_{n + 1} - F_{n + 1 - r} \end{align}$$

share|cite|improve this answer
That's all very nice, but I arrived at the same solution without all that linear algebra. – Brian J. Fink Apr 23 '14 at 2:21
@BrianJ.Fink and of course, with significantly more modesty! – Omnomnomnom Apr 23 '14 at 2:36
Sorry, I had no idea that anyone had answered my question when I answered it. – Brian J. Fink Apr 23 '14 at 2:49
@BrianJ.Fink I like seeing different approaches to the same question, and appreciate you answering as well. One of the great things about the study of mathematics, how different people can solve a problem different ways, but as long as there is no mistake, always arrive at the same answer. – DanielV Apr 23 '14 at 4:38
up vote 3 down vote accepted

Using the formula that I found in this question, I have derived the following: $$\begin{align} f(n,r)&=\sum_{i=1}^r{F_{n-i}}\\ &=\sum_{i=1}^{n-1}{F_i}-\sum_{i=1}^{n-r-1}{F_i}\\ &=F_{n-1+2}-1-F_{n-r-1+2}+1\\ &=F_{n+1}-F_{n-r+1}\\ \\ f(8,6)&=F_{8+1}-F_{8-6+1}\\ &=F_9-F_3\\ &=34-2\\ &=32\\ &=13+8+5+3+2+1\\ &=F_7+F_6+F_5+F_4+F_3+F_2\\ \\ f(7,3)&=F_8-F_5\\ &=21-5\\ &=16\\ &=8+5+3\\ &=F_6+F_5+F_4 \end{align}$$

So it turns out the solution is the difference of two Fibonacci numbers.

share|cite|improve this answer
I wouldn't have posted my answer if I had known that while I was working on it, someone else had already answered my question. Sigh. – Brian J. Fink Apr 23 '14 at 2:47
It's good that you posted an answer, the poster might have preferred an induction based approach rather than a linear algebra based approach. – DanielV Apr 23 '14 at 4:39
@DanielV, I am the poster! LOL – Brian J. Fink Apr 23 '14 at 18:36

Your Answer


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.