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? 

The best approach to get the generating function of a recurrence
is to include directly in it the initial conditions.
In your case, we have
$$
\left\{ \matrix{
  h_{\,n}  = 0\quad \left| {\;n < 0} \right. \hfill \cr 
  h_{\,n}  = 3h_{\,n - 1}  - 4n + 2\left[ {n = 0} \right] \hfill \cr}  \right.
$$
where $[P]$ denotes the Iverson bracket
$$
\left[ P \right] = \left\{ {\begin{array}{*{20}c}
   1 & {P = TRUE}  \\
   0 & {P = FALSE}  \\
 \end{array} } \right.
$$
Then, multiplying by $x^n$ and summing, you get
$$
\eqalign{
  & g(x) = \sum\limits_{0\, \le \,n} {h_{\,n} x^{\,n} }  =   \cr 
  &  = 3\sum\limits_{0\, \le \,n} {h_{\,n - 1} x^{\,n} }  - 4\sum\limits_{0\, \le \,n} {nx^{\,n} }  + 2\sum\limits_{0\, \le \,n} {\left[ {n = 0} \right]x^{\,n} }  =   \cr 
  &  = 3x\sum\limits_{0\, \le \,n} {h_{\,n - 1} x^{\,n - 1} }  - 4x\sum\limits_{0\, \le \,n} {nx^{\,n - 1} }  + 2 =   \cr 
  &  = 3x\left( {h_{\, - 1} x^{\, - 1}  + \sum\limits_{1\, \le \,n} {h_{\,n - 1} x^{\,n - 1} } } \right) - 4x{d \over {dx}}\sum\limits_{0\, \le \,n} {x^{\,n} }  + 2 =   \cr 
  &  = 3x\sum\limits_{0\, \le \,n} {h_{\,n} x^{\,n} }  - 4x{d \over {dx}}\left( {{1 \over {1 - x}}} \right) + 2 =   \cr 
  &  = 3xg(x) - 4x\left( {{1 \over {\left( {1 - x} \right)^{\,2} }}} \right) + 2 \cr} 
$$
that is
$$
\eqalign{
  & \left( {3x - 1} \right)g(x) = {{4x} \over {\left( {1 - x} \right)^{\,2} }} - 2 =  - 2\,{{x^{\,2}  - 4x + 1} \over {\left( {1 - x} \right)^{\,2} }}  \cr 
  & g(x) = 2\,{{x^{\,2}  - 4x + 1} \over {\left( {1 - x} \right)^{\,2} \left( {1 - 3x} \right)}} \cr} 
$$
At this point you can decompose $g(x)$ into partial fractions
$$
g(x) = 2\,{{x^{\,2}  - 4x + 1} \over {\left( {1 - x} \right)^{\,2} \left( {1 - 3x} \right)}} = {2 \over {\left( {1 - x} \right)^{\,2} }} + {1 \over {\left( {1 - x} \right)}} - {1 \over {\left( {1 - 3x} \right)}}
$$
and finally get
$$
h_{\,n}  = 2\left( \matrix{
  n + 1 \cr 
  1 \cr}  \right) + 1 - 3^{\,n}  = 2n + 3 - 3^{\,n} 
$$
