My task is to find formula for generating function of sequence $a_0, a_1...$ defined with following recurence $a_0=1$ and $a_n=\sum_{i=0}^{n-1} (n-i)a_i$.
I rewrote the expression $a_n=\sum_{i=0}^{n-1} (n-i)a_i=n+(n-1)a_1+(n-2)a_2+...+a_{n-1}$ and I counted few members of sequence $a_1=1,a_2=3,a_3=8,a_4=21$ etc.
There are two answears below-wchich one i correct? Is there any way how to do some backward examination to show that it gives correct solution?
On
If we compare this with Fibonacci sequence, we have:
$F_x= 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .$
$.x=1, 2, 3, 4, 5, 6, 7, .8, .9, 10, 11, . . .$
$a_n=. . . 1, . .3, .. .8,. .. 21,. . ..55, . . .$
$n=.. . .1 . . .2. . ..3. . .. .4. . . . .5$
We find that $x=2n$and $c_a=c_F^2$ where $c_F$ is golden ratio and $c_a$ is the ratio of sequence $a_n$. So we may conclude that :
$a_{n+1}=c^2 a_n$
$$a_n=F_x=\frac{1}{\sqrt5}[\frac{1}{1-(\frac{1+\sqrt 5}{2})x}-\frac{1}{1-(\frac{1-\sqrt 5}{2})x}]$$
$x=2n$; $n∈N$.
Consider the relation at $n+1$: $$ a_{n+1}=\sum_{i=0}^{n}(n-i+1)a_i\tag1 $$ Letting $A(x)=\sum_{n\ge 0}a_nx^n$, the LHS is the coeficient of $x^{n}$ in $(A(x)-a_0)/x$, while the the RHS is a convolution, so it is the coefficient of $x^n$ in $$A(x)\cdot \sum_{k\ge 0}(k+1)x^k=A(x)\cdot (1-x)^{-2}.$$ Therefore, multiplying both sides by $x^n$ in $(1)$ and summing over $n\ge 0$, you get $$ (A(x)-1)/x=A(x)\cdot{(1-x)^{-2}}\implies \boxed{A(x)=\frac{(x-1)^2}{1-3x+x^2}.} $$ Here is a Wolfram Alpha sanity check.