Solve the recursion $a_{n} = n a_{n-1} + (n+1)!$

Question

Define the sequence $\{a_{n}\}$ by $a_{n} = n a_{n-1} + (n+1)!$ for $n \geq 1$ and setting $a_{0} = 1$. Solve this recursion completely.

I can solve this rather easily by an induction argument, where I found $a_{n} = \frac{(n+1)!}{2}$. I was not, however, able to solve this using generating functions.

This is a problem from a past exam for one of my classes, and the professor is not fond of induction proofs - so I am thinking that another approach should be possible. If the method of generating functions is not practical, would there be a way to straightforward particular solution one can guess for the inhomogeneous relation?

Answer 1

Hint: Change $a_n=n!b_n$. You get $b_n=b_{n-1}+n+1$.

Answer 2

Hint Use exponential generating functions.

Answer 3

Let $b_n=\dfrac{a_n}{n!}$ and rewrite the recurrence as

$$n!b_n=n(n-1)!b_{n-1}+(n+1)!\;;$$

dividing through by $n!$ leaves you with $b_n=b_{n-1}+(n+1)$, which has the instant solution

$$b_n=b_0+\sum_{k=2}^{n+1}k=\sum_{k=1}^{n+1}k=\frac12(n+1)(n+2)\;.$$

Now just recover $a_n$.