Finding a closed form formula for the sequence defined by $a_{n}=n \cdot (a_{n-1}+a_{n-2})$

Question

Me and some of my friends have been attempting to find a closed form formula for the recurrence relation defined by $a_{n}=n \cdot (a_{n-1}+a_{n-2})$ together with $a_{0}=2$ and $a_{1}=3$. It should be noted that this problem is unrelated to any textbook or course, so we are unsure if a closed form exists at all. Any help solving the problem or determining if the problem has a solution at all is much appreciated.

Answer 1

Generalizing the problem slightly, let $a_0=x$ and $a_1=y$. Then

$$a_2=2(x+y)=2x+2y$$

$$a_3=3((2x+2y)+y)=6x+9y$$

$$a_4=4((6x+9y)+(2x+2y))=32x+44y$$

$$\vdots$$

It is easy to see (and easy to prove by induction) that $a_n=x b_n+y c_n$ where both $b_n$ and $c_n$ are defined in the same manner as $a_n$ with $b_0=1$, $b_1=0$, $c_0=0$, and $c_1=1$. It has been proved (see both oeis pages for references) that for $n\geq 2$ we have

$$b_n=\left\lfloor\frac{e-2}{e}(n+1)! + \frac{1}{2}\right\rfloor$$

$$c_n=\left\lfloor \frac{(n+1)!}{e}+\frac{1}{2}\right\rfloor$$

We conclude that one such formula for $a_n$ is

$$a_n=2\left\lfloor\frac{e-2}{e}(n+1)! + \frac{1}{2}\right\rfloor+3\left\lfloor \frac{(n+1)!}{e}+\frac{1}{2}\right\rfloor$$

(with the stipulation that $a_0=2$ and $a_1=3$). From my quick research I don't believe a 'simpler' formula exists.

Answer 2

Too long for a comment to the original answer by QC_QAOA, but for $n>2,$ we can get a slightly better closed formula.

Essentially, we use $$e^{-1}=\sum_{k=0}^{\infty}(-1)^k \frac1{k!}.$$

So $$\frac{(n+1)!}{e}=\sum_{k=0}^{n+1}(-1)^{k}\frac{(n+1)!}{k!}+\delta_n$$ where $|\delta_n|<\frac{1}{n+2}.$

The expression $\lfloor x+1/2\rfloor$ is the "nearest integer" operator, and $\frac{(n+1)!}{e}$ and $2\frac{(n+1)!}{e}$ are within $\frac{1}{n+1}$ and $\frac2{n+1}$ of an integer, respectively. So, at least for $n>2,$ the exact values will

$$c_n=\sum_{k=0}^{n+1}(-1)^k\frac{(n+1)!}{k!}\\b_n=(n+1)!-2\sum_{k=0}^{n+1}(-1)^k\frac{(n+1)!}{k!}=(n+1)!-2c_n,$$

So $$a_n=2b_n+3c_n=2(n+1)!-c_n=\left\lfloor \frac{(2e-1)(n+1)!}{e}+\frac12\right\rfloor$$

This actually agrees when $n=2,$ as well. It is wrong for $n=0,1.$