Help Solving Recurrence Relation: $a_n = n^3a_{n-1} + (n!)^3$

Question

I'm trying to find an explicit formula for the following recurrence relation:

$a_0 = 1$, $\forall n \ge 1: a_n = n^3a_{n-1} + (n!)^3$

So far though, my attempts have been unsuccessful.

---

My Attempt

Let $A(x) = a_n\frac{x^n}{(n!)^3}$. Multiply by $\frac{x^n}{(n!)^3}$ and sum over $n$ to get:

$$\sum_{n=1}^{\infty}{a_n\frac{x^n}{(n!)^3}} = \sum_{n=1}^{\infty}{a_{n-1}\frac{x^n}{(n-1!)^3}} + \sum_{n=1}^{\infty}{x^n}$$

This can be simplified to:

$$ A(x) - a_0 = xA(x) + \frac{1}{1-x} \\ \implies A(x) = \frac{2-x}{(1-x)^2}$$

Using partial fraction decomposition you recover that $A(x) = \frac{1}{(1-x)} + \frac{1}{(1-x)^2}$, which means that $$A(x) = \sum_{n=0}^{\infty}{x^n} + \sum_{n=0}^{\infty}{(n+1)x^n} \\ \implies A(x) = \sum_{n=0}^{\infty}{(n+2)x^n}$$

Then, to put $A(x)$ back into the form that we defined it in in the beginning, we have: $$A(x) = \sum_{n=0}^{\infty}{(n+2)(n!)^3\frac{x^n}{(n!)^3}} \\ \implies a_n = (n+2)(n!)^3$$

---

I'm wonderring if anyone can provide some insight into where I could have gone wrong. Is the original definition of $A(x)$ valid, or must I stick to either an ordinary / exponential generating function? If so, how could I clear the variable terms in the recurrence?

Answer 1

Hint: Divide by $(n!)^3$ and define $\displaystyle b_n=\frac{a_n}{(n!)^3}$ to get $$ b_n =b_{n-1}+1. $$

Answer 2

One simple way to find these sequences (so simple it is almost cheating!) is to generate the first few terms and search for the resulting sequence in the Online Encyclopedia of Integer Sequences (OEIS). In this case you have:

$$\begin{equation} \begin{aligned} a_0 &= 1, \\[6pt] a_1 &= 1^3 a_0 + (1!)^3 = 1^3 \cdot 1 + 1^3 = 2, \\[6pt] a_2 &= 2^3 a_1 + (2!)^3 = 2^3 \cdot 2 + 2^3 = 24, \\[6pt] a_3 &= 3^3 a_2 + (3!)^3 = 3^3 \cdot 24 + 6^3 = 864, \\[6pt] a_4 &= 4^3 a_3 + (4!)^3 = 4^3 \cdot 864 + 24^3 = 69120, \\[6pt] &\quad \vdots \\[6pt] \end{aligned} \end{equation}$$

Searching the terms 1, 2, 24, 864, 69120 on OEIS leads to a single hit for the integer sequence A172492, which has the form:

$$a_n = (n!)^2 \cdot (n+1)! \quad \quad \quad \text{for all } n = 0,1,2,3,....$$

---

Inductive proof: It is now possible to prove that this form is correct using proof by weak induction. For the base case $n=0$ we have:

$$a_0 = (0!)^2 \cdot (0+1)! = 1^2 \cdot 1! = 1 \cdot 1 = 1.$$

For the inductive step we assume that $a_k = (k!)^2 \cdot (k+1)!$ and we then have:

$$\begin{equation} \begin{aligned} a_{k+1} &= (k+1)^3 a_k + (k+1)!^3 \\[6pt] &= (k+1)^3 \cdot (k!)^2 \cdot (k+1)! + (k+1)!^3 \\[6pt] &= (k+1) \cdot (k+1)!^2 \cdot (k+1)! + (k+1)!^3 \\[6pt] &= (k+1) \cdot (k+1)!^3 + (k+1)!^3 \\[6pt] &= [(k+1) + 1] \cdot (k+1)!^3 \\[6pt] &= (k+2) \cdot (k+1)!^3 \\[6pt] &= (k+1)!^2 \cdot (k+2)!. \\[6pt] \end{aligned} \end{equation}$$

Since the base case is correct, and the inductive step is proved, this proves that the sequence you are dealing with is the integer sequence A172492, with explicit form given above.