Using EGFs to solve the recurrence relation $a_n=n a_{n-1}+(n+1)!$ 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*}$$
 A: 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)!.$$
A: Next step: What is $\sum_{n=1}^\infty x^{n+1}$?
A: Define the exponential generating function:
$\begin{equation*}
\hat{A}(z) = \sum_{n \ge 0} \frac{a_n}{n!} z^n
\end{equation*}$
Write the recurrence shifted:
$\begin{equation*}
a_{n + 1} = (n + 1) a_n + (n + 2)!
\end{equation*}$
Multiply by $z^n / n!$, sum over $n \ge 0$, recognize some sums:
$\begin{align*}
\sum_{n \ge 0} a_{n + 1} \frac{z^n}{n!}
  &= \sum_{n \ge 0} (n + 1) a_n \frac{z^n}{n!}
       + \sum_{n \ge 0} (n + 2)! \frac{z^n}{n!} \\
\hat{A}'(z)
  &= z \hat{A}'(z) + \hat{A}(z)
       + \sum_{n \ge 0} n (n + 1) z^n
\end{align*}$
Now:
$\begin{align*}
\frac{1}{1 - z}
  &= \sum_{n \ge 0} z^n \\
\frac{d^2}{d z^2} \frac{1}{1 - z}
  &= \frac{2}{(1 - z)^3} \\
  &= \sum_{n \ge 0} (n + 2) (n + 1) z^n
\end{align*}$
thus:
$\begin{equation*}
\sum_{n \ge 0} n (n + 1) z^n
  = \frac{2 z}{(1 - z)^3}
\end{equation*}$
Thus you get the differential equation:
$\begin{equation*}
(1 - z) \hat{A}'(z) = \hat{A}(z) + \frac{2 z}{(1 - z)^3}
\end{equation*}$
This one is linear of the first order. For initial condition you know that $\hat{A}(0) = a_0 = 1$, so (written as partial fractions):
$\begin{equation*}
\hat{A}(z)
  = \frac{2}{1 - z}
      - \frac{2}{(1 - z)^2}
      + \frac{1}{(1 - z)^3}
\end{equation*}$
Expanding by the binomial theorem:
$\begin{align*}
  \hat{A}(z)
    &= \sum_{n \ge 0} 2 z^n
         - \sum_{n \ge 0} 2 \binom{-2}{n} (-z)^n
         + \sum_{n \ge 0} \binom{-3}{n} (-z)^n \\
    &= \sum_{n \ge 0} 2 z^n
         - \sum_{n \ge 0} 2 \binom{n + 1}{1} z^n
         + \sum_{n \ge 0} \binom{n + 2}{2} n^n \\
    &= \sum_{n \ge 0}
         \left(
           2 - 2 (n + 1) + \frac{(n + 2) (n + 1)}{2} 
         \right) z^n \\
    &= \sum_{n \ge 0} \frac{n^2 - n + 2}{2} z^n
\end{align*}$
The coefficients are:
$\begin{align*}
a_n
  &= n! [z^n] \hat{A}(z) \\
  &= n! (n^2 - n + 2)
\end{align*}$
But note that this whole mess could be avoided by noting that the recurrence is linear, first order. Dividing through by $n!$ gives a simple recurrence in $a_n / n!$.
