<s>[INST] Deriving Closed Form for a Recursion via Generating Functions Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$.
Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain
$$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = \sum2a_{n+1}x^{n+2} - \sum a_nx^{n+2} + \sum 4n3^nx^{n+2}\\ &\implies [A(x) - a_0 - a_1x] = 2x[A(x)-a_0] - x^2A(x) + \sum_n 4n3^nx^{n+2}\end{align*}$$
Is this correct so far?  Is there always a best way to go about rearranging the obtained generating function, or does it vary from problem to problem?  Further, is it simpler to use this method here or to instead obtain a particular solution through undetermined coefficients?  Any help is much appreciated.
Is it possible to decompose $4n3^nx^{n+2}$ into $x^2$$\sum 4n \times 1/(1-3x)$ and does this help?
 [/INST] This is how I would approach this. Of all the terms $4n3^n$does not depend on the $a_i$, so I'll keep that one apart. The first thing is to view an expression obtained from the remaining terms as a multiple of $A(x)$. So first separate
$$
  a_{n+2}-2a_{n-1}+a_n = 4n3^n.
$$
We can recognise the left hand side as the coefficient of $x^{n+2}$ in $(1-2x+x^2)A(x)$. So if we multiply each displayed recursion relation by $x^{n+2}$ and add up, then we get an equation for $(1-2x+x^2)A(x)$, except for the terms of degree${}\leq1$, which are $1-x$ because $a_0=a_1=1$ and $(1-2x)(1+x)\equiv1-x\pmod{x^2}$. So we get
$$
  (1-2x+x^2)A(x) = 1-x+4x^2\sum_{n\geq0}n(3x)^n,
$$
where the term $x^2$ before the summation comes from the fact that $4n3^n$ was multiplied by $x^{n+2}$ rather than by $x^n$.
Now doing the final summation can be done recognising that we can write $n+1=\binom{n+1}n=(-1)^n\binom{-2}n$ and $1=\binom nn=(-1)^n\binom{-1}n$ for all $n\geq0$, so that
$$
 \sum_{n\geq0}n(3x)^n
=\sum_{n\geq0}\left(\tbinom{-2}n-\tbinom{-1}n\right)(-3x)^n
=(1-3x)^{-2}-(1-3x)^{-1}
=\frac{3x}{(1-3x)^2}.
$$
Putting everything together gives
$$
  A(x)=\frac{1-7x+15x^2+3x^3}{(1-x)^2(1-3x)^2},
$$
where the numerator was obtained as $(1-3x)^2(1-x)+4x^2\times 3x$. Working out a concrete expression for the coefficients of $A(x)$ is now standard by partial fraction decomposition.
</s>