watchmath
  • watchmath
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\]
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • 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
watchmath
  • watchmath
yes, sorry it's a typo :\(F_n=F_{n-1}+F_{n-2}\)
anonymous
  • 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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

watchmath
  • watchmath
Thanks :)
anonymous
  • anonymous
No problem :)
watchmath
  • watchmath
Just wondering. Is it possible to have a bijective proof for this?
anonymous
  • 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.
watchmath
  • 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.
anonymous
  • 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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.