How to derive a closed form of a recursion (maybe using generating functions) Let $a_0=9$ and consider the following recurrence relation: $$a_n=36(n+1)2^{n-2}+2a_{n-1},$$ I'm looking for the closed form of $\{a_n\}.$
I have tried using generator functions:
\begin{align*}
f(x)&=\sum_{n=0}^\infty a_nx^n\\
&=9 +\sum_{n=1}^\infty \left(4.5(n+1)2^{n+1}+2a_{n-1}\right)x^n\\
&=9 +4.5\sum_{n=1}^\infty (n+1)2^{n+1}x^n+2\sum_{n=1}^\infty a_{n-1}x^n\\
&=9 +\frac{4.5}{x}\sum_{n=1}^\infty (n+1)2^{n+1}x^{n+1} + 2x\sum_{n=1}^\infty a_{n-1}x^{n-1}\\
&=9 +\frac{4.5}{x}\sum_{n=2}^\infty n2^{n}x^{n} + 2xf(x)
\end{align*}
What should I do next? Is there a quicker way to solve this?
Thanks in advance

We are given that
$$
a_n = 36 (n+1) 2^{n-2} + 2a_{n-1}, \tag{0} 
$$
we find that, for any positive integer $n$, we have
\begin{align}
a_n &= 36 (n+1) 2^{n-2} + 2a_{n-1} \\ 
&= 36 \left( 2^{n-2} \right) (n+1) + 2^1 a_{n-1} \tag{1} \\
&= 36 (n+1)2^{n-2} + 2 \left( 36 (n-1+1) 2^{n-1-2} + 2  a_{n-2} \right) \\ 
& \qquad \mbox{[using $n-1$ in place of $n$ in (0) above ]} \\
&= 36 \left( 2^{n-2} \right) \big( (n+1) + n \big) + 2^2 a_{n-2} \tag{2} \\
&= 36 \left( 2^{n-2} \right) \big( (n+1) + n \big) + 2^2 \left( 36 (n-2+1) 2^{n-2-2} + 2a_{n-2-1} \right) \\
& \qquad \mbox{[ using $n-2$ in place of $n$ in (0) above ]} \\
&= 36 \left( 2^{n-2} \right) \big( (n+1) + n + (n-1) \big) + 2^3 a_{n-3} \tag{3} \\
&= 36 \left( 2^{n-2} \right) \big( (n+1) + n + (n-1) \big) + 2^3 \left( 36 (n-3+1) 2^{n-3-2} + 2a_{n-3-1} \right) \\ 
&\qquad \mbox{[ using $n-3$ in place of $n$ in (0) above ]} \\
&= 36 \left( 2^{n-2} \right) \big( (n+1) + n + (n-1) + (n-2) \big) + 2^4 a_{n-4} \tag{4} \\
&= \ldots \\
&= 36 \left( 2^{n-2} \right) \big( (n+1) + n + (n-1) + (n-2) + \ldots 2 \big) + 2^n a_0 \\
&\qquad \mbox{[ using the pattern suggested by (1), (2), (3), and (4) above ]} \\
&= 36 \left( 2^{n-2} \right) \big( 1 + 2 + \ldots + (n+1) -1 \big) + 2^n (9) \\
&= 9 \left( 2^n \right) \left( \frac{(n+1)(n+2)}{2} - 1 +1 \right) \\
&= 9 \left( 2^n \right) \frac{(n+1)(n+2)}{2} \\
&= 9 (n+1)(n+2) \left( 2^{n-1} \right).
&= 
\end{align}
Finally, we can use induction to verify that this formula is correct.
