Prove that if $a_0 = 1$ and $a_n = n^2 a_{n-1} + n!^2$, then $a_n = n! (n+1)!$ using generating functions The problem statement is above.
I know via OEIS that this is true but don't know how to prove it.
So far, I have: $$\sum_{n \ge 1} a_n \frac{x^n}{n!} = \sum_{n \ge 1} n^2 a_{n-1} \frac{x^n}{n!} + \sum_{n \ge 1} n! \cdot x^n.$$
This rewrites itself as: $$A(x) - 1 = x\sum_{n \ge1} a_{n-1} \frac{x^{n-1}}{(n-1)!} \cdot n + \sum_{n \ge 1} n! \cdot x^n.$$
For the first sum, how do I work with that extra factor of $n$? For the second sum, is there a way for me to simplify that?
Thanks for any help.
 A: One solution is to use a kind of generating function one step beyond
ordinary or exponential because the sequence grows too fast. Define the
double exponential (or Bessel) generating function of $\,a_n\,$ as
$$ A(x) := \sum_{n=0}^\infty a_n \frac{x^n}{n!^2}. \tag{1} $$
The recurrence equation to solve is
$$ a_0 = 1 \quad \text{ and } \quad a_n = n^2 a_{n-1} + n!^2. \tag{2} $$
This equation leads immediately to
$$ \sum_{n \ge 1} a_n \frac{x^n}{n!^2} = \sum_{n \ge 1} n^2 a_{n-1} \frac{x^n}{n!^2} + \sum_{n \ge 1} n!^2 \frac{x^n}{n!^2}. \tag{3} $$
Simplify the sums a bit to get
$$ \sum_{n \ge 1} a_n \frac{x^n}{n!^2} = \sum_{n \ge 1} a_{n-1} 
\frac{x^n}{(n\!-\!1)!^2} + \sum_{n \ge 1} {x^n}. \tag{4} $$
Now use the definition of $\,A(x)\,$ and sum the geometric series to get
$$ A(x)-1 = x A(x) + \frac{x}{1\!-\!x}. \tag{5} $$
Solve this algebraic equation for $\,A(x)\,$ and use the power series
for $\,\dfrac1{(1\!-\!x)^2}\,$ to get
$$ A(x) = \frac1{(1\!-\!x)^2} = \sum_{n\ge 0} (n\!+\!1)\,x^n =
\sum_{n\ge 0}  (n\!+\!1)\,n!^2\frac{x^n}{n!^2} . \tag{6} $$
This implies that $\,a_n = (n\!+\!1)\,n!^2 = n!(n+1)!. \,$
A: We have
$$\frac{a_{n+1}}{n!(n+1)!} = \frac{n^2a_{n}}{n!(n+1)!} + \frac{n!^2}{n!(n+1)!}\iff \frac{a_{n+1}}{n!(n+1)!} = \frac{a_{n}}{n!(n-1)!}\frac{n}{n+1} + \frac{1}{n+1} $$
Define $y_n = \frac{a_n}{n!(n-1)!}$ then
$$y_{n+1}=\frac{n}{n+1}y_n +\frac{1}{n+1}$$
$$\iff(n+1)(y_{n+1}-1)=n(y_n-1)$$
$$\iff n(y_n-1)=\dots=0(y_0-1)=0$$
Then
$$y_n =1$$
or
$$a_n = n!(n+1)!$$
A: Notice that the power series $\sum n!x^n$ has radius of convergence $0$, so the method is probably doomed from its premises.
But when you want to eliminate powers of $n$ in an induction relation, you can set $a_n=n!b_n$ and reduce it to a simpler one, this is due to the fact that factorial verifies $F_{n+1}=(n+1)F_n$.
Application of this technique here gives
$n!\,b_n=n^2(n-1)!\,b_{n-1}+n!^2=n\,n!\,b_{n-1}+n!^2=n!\,(n\,b_{n-1}+n!)\iff b_n=nb_{n-1}+n!$
By the same method let set $b_n=n!c_n$
$n!\,c_n=n\,(n-1)!\,c_{n-1}+n!=n!\,(c_{n-1}+1)\iff c_n=c_{n-1}+1\iff c_n=c_0+n$
And $a_0=1$ gives $c_0=1$.
