Product of two generating functions in terms of the ordinary generating function? (recurrence relation solving)

Question

I have the following recurrence relation that I am trying to solve: $a_0 = 1$

$$ a_n = \sum_{i = 0}^{n-1} (i+1)a_i$$

for $ n \geq 1$. Let's define $A(x) = \sum_{n= 0}^\infty a_nx^n$, so multiplying the recurrence above by $x^n$ and summing over $n \geq 1$ we get the following $$ A(x) - a_0= \sum_{n \geq 1} \left(\sum_{i = 0}^{n-1} (i+1)a_i\right) x^n$$ and I am quite stuck on how to continue from here, now I know that $$ \frac{xA(x)}{1-x} = \sum_{n \geq 1} \left(\sum_{i = 0}^{n-1} a_i\right) x^n $$ but I'm stuck on how to evaluate the expression with the $i+1$, may anyone point me in the right direction?

Answer 1

Continuing this approach yields \begin{align} A(x)-a_0&=\sum_{n=1}^\infty \left(\sum_{i = 0}^{n-1} (i+1)a_i\right) x^n\\ &= \sum_{i=0}^\infty (i+1)a_i \sum_{n=i+1}^\infty x^n \\ &= \sum_{i=0}^\infty (i+1)a_i \frac{x^{i+1}}{1-x} \\ &= \frac{x}{1-x} \sum_{i=0}^\infty (i+1)a_i x^i \\ &= \frac{x}{1-x}\cdot \frac{d}{dx} \sum_{i=0}^\infty a_i x^{i+1} \\ &= \frac{x}{1-x}\cdot \frac{d}{dx} (x A(x)) \\ &= \frac{x}{1-x} (x A'(x)+A(x)). \end{align} So $$A(x)= \frac{1-x+x^2 A'(x)}{1-2x}.$$ But solving this differential equation doesn't look straightforward.

---

Let's instead obtain a simpler recurrence. We have $a_0=1$ and $a_1=(0+1)a_0=1$. For $n \ge 2$, $$a_n=\sum_{i=0}^{n-1} (i+1)a_i=\sum_{i=0}^{n-2} (i+1)a_i+n a_{n-1}= a_{n-1}+n a_{n-1}=(n+1) a_{n-1}.$$ Iterating yields $$a_n = (n+1) a_{n-1} = (n+1)n a_{n-2}=(n+1)n(n-1)\cdots 3 a_1 = \frac{(n+1)!}{2}$$ for $n \ge 2$, and this formula also works for $n=1$.

Answer 2

Starting from @RobPratt's answer, the differential equation$$A(x)= \frac{1-x+x^2 A'(x)}{1-2x}$$ is not the most pleasant but it can be solved.

Let $A(x)=\frac {B(x)}{x^2}$ to get $$B(x)=x^2 \left(B'(x)-x+1\right)$$ Now, and this has been the most difficult part for me, let $B(x)=e^{-1/x} C(x)$ to get $$C'(x)=e^{\frac{1}{x}} (x-1)$$ which is separable $$C(x)=c_1+\frac{1}{2} \left(\text{Ei}\left(\frac{1}{x}\right)+e^{\frac{1}{x}} (x-1) x\right)$$ Back to $A(x)$ $$A(x)=c_1\frac{ e^{-1/x}}{x^2}+\frac {e^{-1/x} \text{Ei}\left(\frac{1}{x}\right)+(x-1) x } {2x^2}$$

which does not seem to be the simplest way to get the nice result @RobPratt gave in his answer.

Answer 3

Generalizing $a_n = \sum_{i = 0}^{n-1} (i+1)a_i $, if $a_n = \sum_{i = 0}^{n-1} b_ia_i $ then

$\begin{array}\\ a_1 &= b_0a_0\\ \text{and} &\text{if } n \ge 1\\ a_{n+1} &= \sum_{i = 0}^{n} b_ia_i\\ &= \sum_{i = 0}^{n-1} b_ia_i+b_na_n\\ &= a_n+b_na_n\\ &= (b_n+1)a_n\\ \text{so}\\ \dfrac{a_{n+1}}{a_n} &=b_n+1\\ \text{and}\\ \dfrac{a_{m+1}}{a_1} &=\prod_{n=1}^m \dfrac{a_{n+1}}{a_n}\\ &=\prod_{n=1}^m (b_n+1)\\ \text{so}\\ a_m &=a_1\prod_{n=1}^{m-1} (b_n+1)\\ \end{array} $

If $b_n = n+1$ then $a_m =a_1\prod_{n=1}^{m-1} (b_n+1) =\prod_{n=1}^{m-1} (n+2) =\prod_{n=3}^{m+1} n =\dfrac{(m+1)!}{2} $.

Check.

$a_n = \sum_{i = 0}^{n-1} (i+1)a_i $, so $a_1 =a_0 =1 =\dfrac{2!}{2} $, $a_2 =a_0+2a_1 =3 =\dfrac{3!}{2} $, $a_3 =a_0+2a_1+3a_2 =12 =\dfrac{4!}{2} $.