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.
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$.