I have a Recurrence: $$a_{0}=1$$ $$ a_{n}=\sum_{k=0}^{n-1}(n-k)a_{k}$$ I have evaluated some a's:$a_{0}=1, a_{1}=1,a_{2}=3,a_{3}=8,a_{4}=21,a_{5}=55,...$. In the previous exercise on had to derive a generating Function for the even indexted Fibonacci Numbers. So these are definitely $F_{0}=1,F_{1}=1,F_{2}=3,F_{3}=8,F_{4}=21,...$

Then I had a detailed look on the summation: $$a_{0}=1$$ $$a_{1}=(1-0)*1=1$$ $$a_{2}=(2-0)*a_{0}+(2-1)*a_{1}=2*1+1*1=3$$ $$a_{3}=(3-0)*a_{0}+(3-1)*a_{1}+(3-2)*a_{2}=3*1+2*1+1*3=8$$ $$a_{4}=(4-0)*a_{0}+(4-1)*a_{1}+(4-2)*a_{2}+(4-3)*a_{3}=4*1+3*1+2*3+1*8=21$$

Its obviously linked to: Summation of Fibonacci numbers $F_n$ with $n$ odd vs. even

But i dont see how to proceed.

  • $\begingroup$ Shouldn't it then be $a_0=0$? $\endgroup$ – lhf Jun 3 '18 at 11:46
  • $\begingroup$ its 1, i think it uses $F_0=1, and F_1=1$, might be a typo, but its says $a_0 =1$ $\endgroup$ – thetha Jun 3 '18 at 11:47

The right-hand side is the convolution of sequences $\{n\}$ and $\{a_n\}$ (the term $0a_n$ is simply omitted). Taking the ordinary generating functions of both sides, we get $$ A(x)-1=\frac{x}{(1-x)^2}A(x), $$ so that $$ A(x)=\frac{(1-x)^2}{1-3x+x^2}=1+\frac{x}{1-3x+x^2}, $$ and thus $$ a_n=F_{2n}, \quad n\ge 1, $$ where the sequence $\{F_n\}$ starts with $F_0=0$, $F_1=1$.

  • $\begingroup$ I dont untderstand the -1? the right side has an index shift with +1 right? $\endgroup$ – thetha Jun 3 '18 at 16:05
  • $\begingroup$ @thetha No, there is no shift since $(n-k)+k=n$, not $n-1$. There is simply a missing summand of $0a_n$ on the right that extends the sum to $k=n$. Since it doesn’t contribute anything, nothing is subtracted on the right in the functional equation. The $-1$ on the left is there because the convolution on the right has $0$th term equal to $0$ whereas $a_0=1$. $\endgroup$ – Alexander Burstein Jun 3 '18 at 16:09
  • $\begingroup$ Okey i think i dont get you solution. I know I have a sequence (1,2,3,4,5,6....) the generating Function for this one is $\sum_{n \ge 0}(n+1) z^n=\frac{1}{(1-z)^2}$ When i multiplay this with x its a shift of the inder one to the right. Then i get $\frac{x}{(1-x)^2}$ $\endgroup$ – thetha Jun 3 '18 at 16:20
  • $\begingroup$ @thetha That’s equivalent to what I did. $\endgroup$ – Alexander Burstein Jun 3 '18 at 16:34
  • $\begingroup$ Thank you for the Explantation $\endgroup$ – thetha Jun 3 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.