Take the 2-minute tour ×
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.

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|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 at 22:38
    
Sorry, @StevenStadnicki, this is NOT a homework question. Feel free to give an answer. –  Brian J. Fink Apr 22 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 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 at 22:53
    
@Steve I guess the constant will cancel out in that case. –  Brian J. Fink Apr 22 at 22:55

2 Answers 2

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|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 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 at 4:39
    
@DanielV, I am the poster! LOL –  Brian J. Fink Apr 23 at 18:36

$$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|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 at 2:21
    
@BrianJ.Fink and of course, with significantly more modesty! –  Omnomnomnom Apr 23 at 2:36
    
Sorry, I had no idea that anyone had answered my question when I answered it. –  Brian J. Fink Apr 23 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 at 4:38

Your Answer

 
discard

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.