Using EGFs to solve the recurrence relation $a_n=n a_{n-1}+(n+1)!$

Question

I have to solve the recurrence relation

$$a_n = na_{n-1} + (n + 1)!,\qquad a_0 = 1.$$

I am struggling to finish the problem. I have attached my work. Can you please help me finish?

$$\begin{eqnarray*}A(x)&=&\sum_{n\geq 0}\frac{a_n}{n!}x^n = a_0+\sum_{n\geq 1}\frac{a_n}{n!}x^n=a_0+\sum_{n\geq 1}\left(na_{n-1}+(n+1)!\right)\frac{x^n}{n!}\\&=&a_0+\sum_{n\geq 1}a_{n-1}\frac{x^n}{(n-1)!}+\sum_{n\geq 1}(n+1)x^n = a_0 + x \sum_{n\geq 1}a_{n-1} \frac{x^{n-1}}{(n-1)!}+\sum_{n\geq 1}(n+1)x^n\\&=&a_0+ x\,A(x)+\underbrace{\sum_{n\geq 1}(n+1)x^n}_{\text{I know that }(n+1)x^n = \frac{d}{dx}x^{n+1}.}\end{eqnarray*}$$

Answer 1

Next step: What is $\sum_{n=1}^\infty x^{n+1}$?

Answer 2

By differentiating a geometric series and simplifying we get $$ a_0+\sum_{n\geq 1}(n+1)x^n = 1+\frac{d}{dx}\left(\frac{x^2}{1-x}\right)=\frac{1}{(1-x)^2},$$

$$ A(x) = x\,A(x)+\frac{1}{(1-x)^2},\qquad A(x)=\frac{1}{(1-x)^3}\stackrel{\text{stars and bars}}{=}\sum_{n\geq 0}\binom{n+2}{2}x^n $$ hence $$ a_n = \binom{n+2}{2}n! = \color{blue}{\frac{1}{2}(n+2)!}. $$ Let's check it, too: $$ na_{n-1}+(n+1)! = \frac{1}{2}n(n+1)!+(n+1)! = \frac{n+2}{2}(n+1)!\stackrel{\color{green}{\checkmark}}{=}\frac{1}{2}(n+2)!.$$