## watchmath 4 years ago Let $$\{F_n\}$$ be the Fibonacci sequence: $$F_0=1, F_1=1$$ and $$F_n=F_n+F_{n-1}$$ for $$n\geq 2$$. Show that $\sum_{i=0}^n (n-i)F_i=F_{n+3}-n-3$

1. anonymous

Fn = Fn + Fn-1 doesn't make any sense to me, first because that isn't a valid statement (it's like saying x = x + 1 where x = 2, thus 2 = 3 or 1 = 0) and also because the real Fibonacci sequence is: Fn = Fn-1 + Fn-2 unless i'm missing something and am just too tired to thoroughly think it out

2. watchmath

yes, sorry it's a typo :$$F_n=F_{n-1}+F_{n-2}$$

3. anonymous

Induction should be sufficient to prove it. For n=0, you have that $\sum_{i=0}^n-iF_i=0=3-0-3=F_3-n-3$ Now assume the claim for n=k. Then for n=k+1, you have that $\sum_{i=0}^{k+1}(k+1-i)F_i=\sum_{i=0}^{k}(k+1-i)F_i$ $=\sum_{i=0}^k\left((k-i)F_i+F_i\right)=\sum_{i=0}^k(k-i)F_i+\sum_{i=0}^k F_i$ $=F_{k+3}-k-3+\sum_{i=0}^k F_i$ Using a common identity, which itself is a simple proof by induction, you have that $\sum_{i=0}^k F_i=F_{k+2}-1$ Thus, inserting that into the above equation gives $=F_{k+3}-k-3+F_{k+2}-1 = F_{k+4}-k-1-3$ $=F_{(k+1)+3}-(k+1)-3$ and the claim is proven.

4. watchmath

Thanks :)

5. anonymous

No problem :)

6. watchmath

Just wondering. Is it possible to have a bijective proof for this?

7. anonymous

What do you mean? Do you mean that if a_n is a sequence such that $\sum_{i=0}^n(n-i)a_i=a_{n+3}-n-3$ then it is the Fibonacci sequence? That seems to be a much harder question and I'm not even confident that it is true. There are a lot of sequences after all! I'd guess that (if it is true), using induction would also allow you to go in reverse, though the steps might be a bit harder. You also may need to put some constraints on the sequence to make this a true statement.

8. watchmath

No, I mean there is a concrete object that we can count that gives the LHS and the RHS. For example the identity $2^n=\sum_{k=0}^n {n\choose k}$ counts the number of subsets of $$\{1,2,\ldots,n\}$$ in two ways.

9. anonymous

Ah, I'm not sure. Since the Fibonacci numbers often correspond to seashell type patterns, maybe it is possible that the sum over (n-i)F_i has some sort of geometric interpretation that can be altered in some clever way to make it look like the RHS. If there is a counting argument that can show this, something along those lines would be my best guess.