Htykuut

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_{mgeq0}frac1{m!Gamma(m+alpha+1)}bigg(frac x2bigg)^{2m+alpha}$$
Is the modified Bessel Function of the second kind.

And
$$K_alpha(x)=fracpi2frac{I_{-alpha}(x)-I_alpha(x)}{sinpialpha}$$
Is the modified bessel function of the second kind.

How does one derive this formula?

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

$$
frac{2alpha}{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$

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.