$a_n=(n-1)a_{n-1}+a_{n-2}$

Question

In an answer to a recent question of mine, I was introduced to the recurrence relation $$a_n=(n-1)a_{n-1}+a_{n-2}$$ Where $a_1=0,a_2=1$. I have computational evidence that $a_n=a_{-n}$, as I have computed up to $a_{10}=516901$, and $a_{-10}=516901$. But, so far I don't really see a pattern in the numbers which could help me with my closed form. Of course, there's the patterns one gets by using the general case, $$a_n=(n-1)\bigg[(n-2)a_{n-2}+a_{n-3}\bigg]+a_{n-2}$$ $$a_n=(n-1)\bigg[(n-2)\bigg[(n-3)a_{n-3}+a_{n-4}\bigg]+a_{n-3}\bigg]+a_{n-2}$$ And so on. These patterns suggest some sort of series of factorials of various types, yet I do not think that going on and on like that would be very productive. As you can see, I am pretty lost.

I heard that one could express this sort of recurrence relation with hypergeometric functions. Does anyone know how to do this? Thanks.

Update:

The OEIS proposes that the relation has the formula $$a_n=2K_1(2)I_n(-2)+2I_1(2)K_n(2)$$ Where $$I_\alpha(x)=\sum_{m\geq0}\frac1{m!\Gamma(m+\alpha+1)}\bigg(\frac x2\bigg)^{2m+\alpha}$$ Is the modified Bessel Function of the second kind.

And $$K_\alpha(x)=\frac\pi2\frac{I_{-\alpha}(x)-I_\alpha(x)}{\sin\pi\alpha}$$ Is the modified bessel function of the second kind.

How does one derive this formula?

Answer 1

The modified Bessel functions of the first kind have the recurrence relation

$$ \frac{2\alpha}{x}C_{\alpha}(x) = C_{\alpha - 1}(x) - C_{\alpha + 1}(x) \tag{1} $$

where $C_\alpha$ denotes $I_\alpha$, $e^{\alpha i \pi} K_\alpha$. Take $\alpha = n-1$ and $x = 2$

$$ C_{n} (2) = -(n - 1)C_{n-1}(2) + C_{n-2}(2) \tag{2} $$

And you can see from here that this looks already looks a lot like your problem. For example, if you take $I_n$, then you have

$$ I_n(2) = -(n - 1)I_{n-1}(2) + I_{n-2}(2) \tag{3} $$

The problem is the sign in the first term, but that one is easy to figure out, because the $I_n$ has the parity of $n$. So if $n$ is even, $n$ is odd and you can move the minus to the argument. If $n$ is odd, $n-1$ is even, and you can multiply by $-1$ everything and move the sign to the argument again. You can repeat the same analysis for $K$ and reach the conclusion that

$$ a_n = c_1 I_n(-2) + c_2 K_n(2) \tag{4} $$

The constants $c_1$ and $c_2$ you can find with the seeds $a_1 = 0$, $a_2 = 1$

Answer 2

Hint to show $a_n=a_{-n}$: Let $b_n=a_{-n}$, and see that $b_0=1$, $b_1=0$, $b_2=2$. Now

$$a_n=(n-1)a_{n-1}+a_{n-2}$$

Substituting $n=-k+2$,

$$a_{-k+2}=(-k+1)a_{-k+1}+a_{-k}$$

$$b_{k-2}=(-k+1)b_{k-1}+b_k$$

$$b_k=(k-1)b_{k-1}+b_{k-2}.$$

So, $b_n$ has the same first recurrence relation as $a_n$ and it also has the same first two terms, so we can show (by induction) that $b_n=a_n$ for all $n$.

Finding a closed form is likely to be difficult: for example, the OEIS entry has no such form.