Find Nth formula of recursive formula $a_n=a_{n-1}+n(n-1)a_{n-2}$

Question

$$a_n=a_{n-1}+n(n-1)a_{n-2}$$
$$a_0=1, a_1=-\frac{1}{2}$$
Is it possible to find explicit formula for $a_n$ just by using $a_0$ and $a_1$?
I know how to solve this problem if $a_n=Aa_{n-1}+Ba_{n-2}$ where $A$ and $B$ is some real number(constant), but in this problem that is not a case.

Answer 1

For the second question, note that

$$\begin{align*}\begin{bmatrix}a_n\\a_{n-1}\end{bmatrix}&=\begin{bmatrix}Aa_{n-1}+Ba_{n-2}\\ a_{n-1}\end{bmatrix}=\begin{bmatrix}A &B\\ 1 & 0\end{bmatrix}\begin{bmatrix}a_{n-1}\\a_{n-2}\end{bmatrix}=\begin{bmatrix}A&B\\1&0\end{bmatrix}^2\begin{bmatrix}a_{n-2}\\ a_{n-3}\end{bmatrix}\\&=\cdots=\begin{bmatrix}A&B\\1&0\end{bmatrix}^{n-2}\begin{bmatrix}a_1\\a_0\end{bmatrix}\end{align*}$$

With a similar argument, we would get that

$$\begin{align*}\begin{bmatrix}a_n\\a_{n-1}\end{bmatrix}&=\begin{bmatrix}a_{n-1}+n(n-1)a_{n-2}\\ a_{n-1}\end{bmatrix}=\begin{bmatrix}1 &n(n-1)\\ 1 & 0\end{bmatrix}\begin{bmatrix}a_{n-1}\\a_{n-2}\end{bmatrix}\\&=\begin{bmatrix}1&n(n-1)\\1&0\end{bmatrix}\begin{bmatrix}1 &(n-1)(n-2)\\1&0\end{bmatrix}\begin{bmatrix}a_{n-2}\\ a_{n-3}\end{bmatrix}\\&=\cdots \\&=\left(\prod_{k=0}^{n-2} \begin{bmatrix}1&(n-k)(n-k-1)\\1&0\end{bmatrix}\right)\begin{bmatrix}a_1\\a_0\end{bmatrix}\end{align*}$$

Answer 2

Let $\displaystyle\;b_n = \frac{a_n}{n!}$, the recurrence relation at hand can be transformed to

$$n ( b_n - b_{n-2} ) = b_{n-1}\quad\text{ with }\quad \begin{cases} b_0 = 1\\b_1 = -\frac12\end{cases}\tag{*1}$$

Let $f(z) = \sum_{n=0}^\infty b_n z^n$ be the OGF for $b_n$. If we multiple $(*1)$ by $z^n$ and start to sum from $n = 2$. We get

$$\begin{align} & z\frac{d}{dz}\left[ (1-z^2) f(z) - 1 + \frac{z}{2} \right] = z(f(z)-1)\\ \iff & (1-z^2) \frac{df(z)}{dz} - (1+2z) f(z) = -\frac{3}{2} \end{align} $$ Solving the ODE gives us

$$f(z) = \frac{5 - 3\sin^{-1}(z)}{2(1-z)\sqrt{1-z^2}} - \frac{3}{2(1-z)}$$

Expanding $f(z)$ as a power series in $z$, we obtain following ugly expression of $a_n$.

$$a_n = \frac{n!}{2}\left[ 5\sum_{p=0}^{\lfloor \frac{n}{2}\rfloor} \frac{\binom{2p}{p}}{4^p} - 3\sum_{s=0}^{\lfloor\frac{n-1}{2}\rfloor} \sum_{p=0}^s \frac{\binom{2p}{p}\binom{2s-2p}{s-p}}{4^s(2p+1)} - 3 \right]$$ As a double check, the first few values of $a_n$ according this formula are

$$(2a_0,2a_1,\ldots) = 2, -1, 3, -3, 33, -27, 963, -171, 53757, 41445,4879575, 9438525, \ldots$$

and they do satisfy the recurrence relation.

Update

It turns out we can simplify the mess a little bit.

The recurrence relation on $b_n$ can be rewritten as $b_n = (n+1)(b_{n+1} - b_{n-1})$. The RHS has the form of a finite difference. We can use it to get rid of one level of summation. The end result is for all $n \ge 0$,

$$a_n = \frac{(n+1)!}{2}\left[ 5\frac{\binom{2r}{r}}{4^r} - 3\sum_{p=0}^s \frac{\binom{2p}{p}\binom{2s-2p}{s-p}}{4^s(2p+1)} \right] \quad\text{ with }\quad \begin{cases} r = \lfloor \frac{n+1}{2}\rfloor\\ s = \lfloor \frac{n}{2}\rfloor \end{cases} $$