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?
Asked
Active
Viewed 1,209 times
4
-
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
-
Your edit didn't help. Additionally, in your very last lines you wrote $F_n+ F_{n+1}=F_{n+1}$...? – draks ... Apr 22 '14 at 23:00
-
There, @draks..., I fixed it. Did I make any other mistakes? – Brian J. Fink Apr 22 '14 at 23:05
-
@draks..., Lucas numbers follow the rule $L_n=F_{n+1}+F_{n-1}$. – Brian J. Fink Apr 22 '14 at 23:07
-
If you rewrite every one of these results, on the right-hand side, as the appropriate $$ A F_n + B L_n, $$ you should get an understandable pattern in how $A,B$ change depending on the number of terms summed. I think you can avoid rational coefficients (as opposed to integers only) by switching to $$ A F_{n-1} + B L_{n-1}. $$ – Will Jagy Apr 22 '14 at 23:08
-
@draks... On closer inspection, there does appear to be an error in my $2F_n$ result, but I'm having difficulty spotting where I made it. – Brian J. Fink Apr 22 '14 at 23:31
-
@draks... I found the error. I will complete my edits at another time. Thank you for pointing it out! – Brian J. Fink Apr 22 '14 at 23:56
-
@Steve there was a slight error in your hint, but I appreciate that you pointed me in the right direction. – Brian J. Fink Apr 23 '14 at 02:35
2 Answers
3
$$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}$$
DanielV
- 23,556
-
That's all very nice, but I arrived at the same solution without all that linear algebra. – Brian J. Fink Apr 23 '14 at 02:21
-
-
Sorry, I had no idea that anyone had answered my question when I answered it. – Brian J. Fink Apr 23 '14 at 02:49
-
1@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 04:38
3
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.
Brian J. Fink
- 1,364
-
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 02: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 04:39
-