Solving recurrence using EGF How do I solve the recurrence relation $a_n = na_{n - 1}+ (n - 1)!$ using exponential generating function?
Any help would be highly appreciated. Thanks.
 A: Welcome to MSE!
Let $A = \sum \frac{a_n}{n!} x^n$ be the exponential generating function of $a_n$.
Dividing both sides of the recurrence by $n!$ gives
$$
\frac{a_n}{n!} 
= \frac{na_{n-1}}{n!} + \frac{(n-1)!}{n!} 
= \frac{a_{n-1}}{(n-1)!} + \frac{1}{n}
$$
Then if we multiply both sides by $x^n$ we get
$$
\frac{a_n}{n!}x^n = \frac{a_{n-1}}{(n-1)!}x^n + \frac{1}{n}x^n
$$
and summing over all $n \geq 1$ (being careful of the $a_0$ boundary term) gives
$$
A - a_0 = xA + \sum_{n \geq 1} \frac{1}{n} x^n
$$
We can solve this for $A$:
$$
A = \frac{1}{1-x} \left ( a_0 + \sum \frac{1}{n} x^n \right )
$$
But we know the $x^n$ coefficient of $\frac{a_0}{1-x}$: it's exactly $a_0$.
We also know the $x^n$ coefficeint of $\frac{1}{1-x} \sum \frac{1}{n} x^n$, at least in theory. It turns out that
$$\frac{1}{1-x} \sum_{n \geq 0} c_n x^n = \sum_{n \geq 0} \left ( \sum_{0 \leq k \leq n} c_k \right ) x^n$$
that is, the $x^n$ coefficient is exactly the $n$th partial sum of the original series. You can see this mentioned here or in the excellent book generatingfunctionology (rule 5 on page $37$).
So then by comparing coefficients on both sides, we find
$$\frac{a_n}{n!} = a_0 + \sum_{k \leq n} \frac{1}{n}$$
In other words,
$$a_n = n! (a_0 + H_n)$$
where $H_n$ is the $n$th Harmonic Number.
In case you're feeling doubtful, it's easy to ask
sage to double check that this is true.
Here I've set $a_0 = 1$:


I hope this helps ^_^
