Question

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\]

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

Thanks :)

Answer 5

No problem :)

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

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.