<s>[INST] Solve $h_n = 3h_{n-1} -4n$ using generating functions Solve $h_n = 3h_{n-1} -4n$, where $h_0 = 2$ using generating functions.
I am struggling to figure out how to solve this using generating functions. I know the answer should be $h_n = -3^n +2n + 3$. 
Here is the method that both my textbook and professor used.
Let $g(x) =\sum_{n=0}^{\infty} h_nx^n $. Then let $h_n = 0$  if $n>0$. 
Then $3x g(x)= \sum_{n=0}^{\infty} 3h_nx^{n+1} = \sum_{n=0}^{\infty} 3h_{n-1} x^n $ 
Subtracting these two equations we get  
$(1-3x)g(x) = \sum_{n=0}^{\infty}(h_n - 3h_{n-1})x^n $
$= h_0 + (h_1-3h_0)x + ... + (h_n -3h_{n-1})x^n + ... $
$= 2-4x-8x^2 -...-4nx^n -...$
From here we are suppose to find some sort of pattern to simplify, but all the example have coefficients that can be written as a number to the power n, but here we have -4n instead. How do I compensate for this? 
 [/INST] From where you left off, the first problem is to find the generating function for sequence $a_n = -4n$. This is not so hard if know the relation between operations on generating functions and operations on their corresponding sequences (see here): $\langle a_n \rangle = -4( \langle 1, 1, 1, \cdots \rangle * \langle 1, 1, 1, \cdots \rangle - \langle 1, 1, 1, 1 \cdots \rangle)$, where $*$ is the discrete convolution, which corresponds to multiplication of generating functions. So 
$$\sum_{n = 1}^{\infty} -4nx^n =-4\left( \frac{1}{1-x}\frac{1}{1-x} - \frac{1}{1-x}\right) = \frac{-4x}{(1-x)^2}$$
Another way to get this is to notice that $nx^n = (x^{n+1})' - x^n$, so $$\sum_{n = 0}^{\infty} nx^n = \sum_{n = 0}^{\infty} (x^{n+1})' - \sum_{n = 0}^{\infty} x^n = (\sum_{n = 0}^{\infty} x^{n+1})' - \sum_{n = 0}^{\infty} x^n = (\sum_{n = 1}^{\infty} x^{n})' - \sum_{n = 0}^{\infty} x^n$$
So this evaluates to $(\frac{1}{1-x} - 1)' - \frac{1}{1-x} = \frac{1}{(1-x)^2}$.
So plug this into your result, we get 
$$g(x) = \frac{1}{1-3x}\left(2 - \frac{-4x}{(1-x)^2}\right) = \frac{2x^2 -8x + 2}{(1-x)^2(1-3x)}$$
The only way I know to proceed here is to decompose this function into the following form:
$$\frac{2x^2 -8x + 2}{(1-x)^2(1-3x)} = \frac{Ax + B}{(1-x)^2} + \frac{C}{1-3x}$$
where after computing the right-hand-side out and matching the coefficient, I get $A = -1, B = 3, C = -1$. So, in fact, 
$$g(x) = \frac{3}{(1-x)^2} - \frac{x}{(1-x)^2} - \frac{1}{1-3x}$$
The first term represents $3(n+1)$, the second $n$, and the third $n^3$.
Thus $$h_n = 3(n+1) - n - n^3 = -n^3 + 2n + 3$$.
</s>