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
 A: Note that
$$
\sum_{n\ge1}(n+1)2^{n+1}x^n = \frac{\mathrm{d}}{\mathrm{d}x}\sum_{n\ge1}2^{n+1}x^{n+1} = \frac{\mathrm{d}}{\mathrm{d}x}\left(4x^2\sum_{n\ge0}(2x)^n\right) = \frac{\mathrm{d}}{\mathrm{d}x}\frac{4x^2}{1-2x} = \frac{8x(1+x)}{(1-2x)^2}
$$
In the case where you would like to avoid using the generating function, you could have solved the homogeneous recurrence relation first and then used an ansatz for the particular solution.
But if you want a more systematic way to solve inhomogeneous first-order linear recurrence relation to get a closed form, you can follow my answer here.
A: 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.
A: An easy way to solve this recurrence.
As the recurrence is linear, we have that
$$
a_n = a_n^h + a_n^p
$$
such that
$$
\cases{a_n^h= 2 a_{n-1}^h\\ a_n^p = 2 a_{n-1}^p+36(n+1)2^{n-2}}
$$
so $a_n^h = c_0 2^n$. Now assuming $a_n^p = c_0(n)2^n$ after substitution into the complete equation, we have
$$
c_0(n)2^n = 2c_0(n-1)2^{n-1}+36(n+1)2^{n-2}
$$
or
$$
c_0(n) = c_0(n-1)+9(n+1)
$$
hence
$$
c_0(n) = 9\frac{(n+1)(n+2)}{2}
$$
then
$$
a_n^p = 9\frac{(n+1)(n+2)}{2}2^n
$$
and finally
$$
a_n = \left(9\frac{(n+1)(n+2)}{2}+c_0\right)2^n
$$
