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.
On
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} $$
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!}.$$