<s>[INST] 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.
 [/INST] 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!}.$$
</s>