<s>[INST] Closed form of a recursive relation A sequence $\langle a_n\rangle$ is defined recursively by $a_1=0$, $a_2=1$ and for $n\ge 3$,
$$a_n=\frac 12 na_{n-1}+\frac 12n(n-1)a_{n-2}+(-1)^n\left(1-\frac n2\right).$$
Find a closed form expression for
$$f_n=a_n+2\binom n1a_{n-1}+3\binom n2a_{n-2}+\cdots+(n-1)\binom n{n-2}a_2+n\binom n{n-1}a_1.$$

I substituted $b_k=\binom n{n-k}a_k$ which reduces the given recursion to $$b_n=\frac {b_{n-1}}2+b_{n-2}+(-1)^n\left(1-\frac n2\right)\\ \Longrightarrow2b_n-b_{n-1}-2b_{n-2}=(-1)^n(2-n)\\ \Longrightarrow 2b_{n-1}-b_{n-2}-2b_{n-3}=-(-1)^n(3-n)\\ \Longrightarrow2b_{n-1}-b_{n-2}-2b_{n-3}=-(-1)^n(3-n)\\ \Longrightarrow 2b_{n-2}-b_{n-3}-2b_{n-4}=(-1)^n(4-n)$$ Adding the last four equations, we get $$2b_n+3b_{n-1}-2b_{n-2}-5b_{n-3}-2b_{n-4}=0$$ Now using the standard way of solving such recursions, we set $b_k=\lambda^k$, which gives $$2\lambda^4+3\lambda^3-2\lambda^2-5\lambda-2=0$$ We have to find $f_n=a_n+2\binom n1a_{n-1}+3\binom n2a_{n-2}+\cdots+(n-1)\binom n{n-2}a_2+n\binom n{n-1}a_1\\=b_n+2b_{n-1}+3b_{n-2}+\cdots+(n-1)b_2+nb_1\\=\lambda^n+2\lambda^{n-1}+3\lambda^{n-2}+\cdots+(n-1)\lambda^2+n\lambda$ 

This is where I got stuck. What should I do after this?
 [/INST] Let
$$ f(z) = \sum_{n\geq 0} b_n z^n.\tag{1}$$
Since:
$$ \sum_{n\geq 0}\left(1-\frac{n}{2}\right)(-1)^n z^n = \frac{2+3z}{2(1+z)^2}$$
the recursion on $b_n$ gives:
$$ f(z) = \frac{1}{2}z\,f(z)+z^2\, f(z)+\frac{2+3z}{2(1+z)^2},$$
hence:
$$ f(z) = \frac{2+3z}{(1-z)^2(2-3z^2)}.\tag{2}$$
We want to find:
$$ f_n = n b_1 + (n-1) b_2 + \ldots + 2 b_{n-1} + b_{n} \\= (n+1)(b_1+\ldots+b_n)-(1\cdot b_1 + 2\cdot b_2 +\ldots+ n\cdot b_n)\tag{3}$$
where $b_1+\ldots+b_n$ can be extracted from:
$$ [z^n]\frac{f(z)}{1-z} $$
and $1\cdot b_1 + \ldots + n\cdot b_n $ can be extracted from:
$$ [z^{n-1}]\frac{f'(z)}{1-z},$$
hence it suffices to provide a partial fraction decomposition for the RHS of $(2)$. 
I bet you can finish from here.
</s>