# Explicit Formula of Recurrence Relation from Generating Function

I have given following recurrence relation:

$$a_{n+1} = (n+1)a_n + n!$$ where $a_0 = 0$

I had invoked given relation with exponential generating function, such as:

$$g(x) = \sum_{n=0}^\infty a_n {x^n\over n!} \\= \sum_{n=1}^\infty a_n {x^n\over n!} + a_0 \\= \sum_{n=0}^\infty a_{n+1} {x^{n+1}\over (n+1)!}\\=x\sum_{n=0}^\infty a_n {x^n\over n!}+\sum_{n=0}^\infty{1\over n+1}x^{n+1}$$ thus, $$g(x) = xg(x) + x+\frac{x^2}{2} + \frac{x^3}{3} +\cdots$$ therefore, $$g(x) = {1\over 1-x}(x+\frac{x^2}{2}+\frac{x^3}{3} + \cdots) \tag{1}$$

Now from this $g(x)$ I want to draw out explicit formula of $a_n$ but I can't image the way how I can change RHS of $(1)$ into form of $a_nx^n/n!$

Where should I start from?

• You get that $g(x) = \sum H_n x^n$ is the ordinary generating function of the harmonic numbers $H_n = \sum_{k=1}^n \frac{1}{k}$, so $a_n = n! H_n$. I don't think you can say much more than that. – Qiaochu Yuan Nov 27 '17 at 0:02

If we divide by $(n+1)!$, we get $$\frac{a_{n+1}}{(n+1)!}=\frac{a_n}{n!}+\frac1{n+1}$$ Thus, $$\frac{a_n}{n!}=C+H_n$$ The condition $a_0=0$ implies that $C=0$. Therefore, $$a_n=n!\,H_n$$