Closed form of a recurrence relation containing factorials. Let a sequence $\{x_n\}_{n\ge1}$ defined by $x_n=3nx_{n-1}+n!-3^n(n^2-2);\ \forall n\ge2$ with $x_1=10$. Find a closed form of $x_n$.
I tried that $b_n=\frac{x_n-3^n}{n!}$ then the above reduces into $b_n-3b_{n-1}=\frac{3^n}{n!}-9\cdot\frac{3^{n-2}}{(n-2)!}+1$. Now the left is not telescoping. What to do? Is this the right way to approach? I know generating functions but as the problem comes from an olympiad level contest, it must have some manipulative trick.
 A: Hint. Try with $b_n=\frac{a_n}{n!3^n}$, then the recurrence is
$$b_n=b_{n-1}+\frac{1}{3^n}-\frac{1}{(n-2)!}-\frac{1}{(n-1)!}+\frac{2}{n!}$$
where we used $n^2=n(n-1)+n$.
Hence
$$b_N=b_1+\sum_{n=2}^N \left(\frac{1}{3^n}-\frac{1}{(n-2)!}-\frac{1}{(n-1)!}+\frac{2}{n!}\right)\\
=\frac{10}{3}+\sum_{n=2}^N \frac{1}{3^n}-\sum_{n=2}^N \frac{1}{(n-2)!}-\sum_{n=2}^N \frac{1}{(n-1)!}+\sum_{n=2}^N \frac{2}{n!}\\
=\frac{10}{3}+\sum_{n=2}^N \frac{1}{3^n}-\sum_{n=0}^{N-2} \frac{1}{n!}-\sum_{n=1}^{N-1} \frac{1}{n!}+2\sum_{n=2}^N \frac{1}{n!}\\
=\frac{1}{2}-\frac{1}{2\cdot 3^N}+\frac{N+2}{N!}.$$
A: To get a closed form for
$$
x_n=3nx_{n-1}+n!-3^n(n^2-2)\tag{1}
$$
with $x_0=2$, let $x_n=3^nn!\,y_n$, then $(1)$ becomes
$$
3^nn!\,y_n=3n\,3^{n-1}(n-1)!\,y_{n-1}+n!-3^n(n^2-2)\tag{2}
$$
Divide $(2)$ by $3^nn!$ to get
$$
y_n=y_{n-1}+\frac1{3^n}-\frac{n^2-2}{n!}\tag{3}
$$
Which means that since $y_0=2$,
$$
\begin{align}
y_n
&=y_0+\sum_{k=1}^n\left(\frac1{3^k}-\frac{k(k-1)+k-2}{k!}\right)\\
&=y_0+\frac{1-\frac1{3^n}}2-\sum_{k=0}^{n-2}\frac1{k!}-\sum_{k=0}^{n-1}\frac1{k!}+2\sum_{k=1}^n\frac1{k!}\\
&=y_0+\frac{1-\frac1{3^n}}2+\frac{n+2}{n!}-2\\
&=\frac{1-\frac1{3^n}}2+\frac{n+2}{n!}\tag{4}
\end{align}
$$
Therefore,
$$
\bbox[5px,border:2px solid #C0A000]{x_n=3^nn!\left(\frac{1-\frac1{3^n}}2+\frac{n+2}{n!}\right)}\tag{5}
$$
