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

Question

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.

Answer 1

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)!. \,$

Answer 2

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$.

Answer 3

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)!$$