Solving recurrence using EGF

Question

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.

Answer 1

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 ^_^