Generating function from a summation relation

Question

I have got a summation relation for recurrence:

$a_0$ = 1

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

The question is: How do I make a generating function out of this? The recurrence could be modified to $a_n$ = (n+1)$a_{n-1}$ or $a_n$ = $\frac{(n+1)!}{2}$.

Thanks a lot!

Answer 1

Well, the initial part of the summation is the same for $a_{n+1}$ as for $a_n$, hence you may rewrite it as follows: $$a_{n+1} = \sum_{i=0}^n(i+1)a_i = \underbrace{\sum_{i=0}^{n-1}(i+1)a_i}_\text{hey, that's $a_n$} + (n+1)\cdot a_n = (n+2)\cdot a_n$$ which is exactly what you needed.

Too bad the generating function diverges everywhere, but that's another story.

Answer 2

Use generating function properties. Note that if you define $A(z) = \sum_{n \ge 0} a_n z^n$, note that:

$\begin{align*} \sum_{n \ge 0} (n + 1) a_n z^n &= \frac{d}{d z} z A(z) \\ &= A(z) + z A'(z) \\ \end{align*}$

Also, shift the recurrence by one, multiply by $z^n$, sum over $n \ge 0$ amd recognize some sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 1} z^n &= \sum_{n \ge 0} z^n \sum_{0 \le k \le n} (k + 1) a_k \\ \frac{A(z) - a_0}{z} &= \frac{A(z) + z A'(z)}{1 - z} \end{align*}$

The result is a linear differential equation of the first order, you know also that $A(0) = a_0$ as initial value. It's solution is given in terms of non-elementary functions.