Closed form of a recursive relation

Question

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?

Answer 1

With Abhishek Bakshi hint ,Now I have complete this answer,

since $$\dfrac{a_{n}}{n!}=\dfrac{1}{2}\dfrac{a_{n-1}}{(n-1)!}+\dfrac{1}{2}\dfrac{a_{n-2}}{(n-2)!}+\dfrac{(-)^n(1-\dfrac{n}{2})}{n!}$$ let $b_{n}=\dfrac{a_{n}}{n!},b_{1}=0,,b_{2}=\dfrac{1}{2} $then we have $$b_{n}=\dfrac{1}{2}b_{n-1}+\dfrac{1}{2}b_{n-2}+\dfrac{(-)^n(1-\dfrac{n}{2})}{n!}$$ $$\Longrightarrow b_{n}-b_{n-1}=-\dfrac{1}{2}(b_{n-1}-b_{n-2})+\dfrac{(-)^n(1-\dfrac{n}{2})}{n!}$$ let $b_{n}-b_{n-1}=c_{n},c_{2}=\dfrac{1}{2}$,then we have $$2c_{n}+c_{n-1}=\dfrac{2(-1)^n}{n!}+\dfrac{(-1)^n}{(n-1)!}$$ so $$c_{n}=\dfrac{(-1)^n}{n!}+C$$ since $c_{2}=\dfrac{1}{2}\Longrightarrow C=0,$,so $$c_{n}=\dfrac{(-1)^n}{n!}\Longrightarrow b_{n}=b_{n-1}+\dfrac{(-1)^n}{n!}$$ and since $$f_{n}=a_{n}+2\binom{n}{1}a_{n-1}+\cdots+(n-1)\binom{n}{n-2}a_{2}+n\binom{n}{n-1}a_{1},a_{1}=0$$ so \begin{align*}\dfrac{f_{n}}{n!}&=\dfrac{a_{n}}{n!}+2\dfrac{b_{n-1}}{(n-1)!}+\cdots+\dfrac{(n-1)}{(n-2)!}\dfrac{a_{2}}{2!}\\ &=b_{n}+2b_{n-1}+\dfrac{3}{2!}b_{n-2}+\cdots+\dfrac{n-1}{(n-2)!}b_{2} \end{align*} so we have \begin{align*}\dfrac{f_{n+1}}{(n+1)!}-\dfrac{f_{n}}{n!}&=\left(b_{n+1}+2b_{n}+\cdots+\dfrac{n}{(n-1)!}b_{2}\right)-\left(b_{n}+2b_{n-1}+\cdots+\dfrac{n-1}{(n-2)!}b_{2}\right)\\ &=(b_{n+1}-b_{n})+2(b_{n}-b_{n-1})+\dfrac{3}{2!}(b_{n-1}-b_{n-2})+\cdots\\ &=\dfrac{(-1)^{n+1}}{n+1}+\dfrac{2(-1)^n}{n!}+\dfrac{3(-1)^{n-1}}{2!(n-1)!}+\cdots+\dfrac{n}{2!(n-1)!} \end{align*} let $$A_{n}=\dfrac{(-1)^{n+1}}{n+1}+\dfrac{2(-1)^n}{n!}+\dfrac{3(-1)^{n-1}}{2!(n-1)!}+\cdots+\dfrac{n}{2!(n-1)!}$$ so we have $$(-1)^{n+1}(n+1)!A_{n}=1-2\binom{n+1}{1}+3\binom{n+1}{2}+\cdots+(-1)^{n-1}n\binom{n+1}{n-1}$$ Note \begin{align*}(1-1)^{n+1}&=1-\binom{n+1}{1}+\binom{n+1}{2}+\cdots+(-1)^{n-1}\binom{n+1}{n-1}+(-1)^n(n+1)+(-1)^{n+1}\\ &=0 \end{align*} and use well know indentity $$k\binom{n+1}{k}=(n+1)\binom{n}{k-1}$$ so \begin{align*} &-\binom{n+1}{1}+2\binom{n+1}{2}+\cdots+(-1)^{n+1}(n+1)\binom{n+1}{n+1}\\ &=-(n+1)[\binom{n}{0}-\binom{n}{1}+\cdots+(-1)^n\binom{n}{n}]\\ &=0 \end{align*} so we have $$(-1)^{n+1}(n+1)!A_{n}=(-1)^{n+1}(n^2+n-1)$$ so $$\dfrac{f_{n+1}}{(n+1)!}-\dfrac{f_{n}}{n!}=\dfrac{n^2+n-1}{(n+1)!}=\dfrac{n+1}{n!}-\dfrac{n+2}{(n+1)!}$$ so $$\dfrac{f_{n}}{n!}=C-\dfrac{n+1}{n!}$$,note $f_{1}=0\Longrightarrow C=2$ so $$f_{n}=2n!-(n+1)$$

Answer 2

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.