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? 
 A: Good start! You have
$$(1-3x) g(x) = 2 - 4\sum_{n=1}^\infty n x^n$$
so the real question is how can you find a nicer expression for the series 
$\sum_{n=1}^\infty n x^n$. One way of doing this is to observe
$n x^{n-1} = \frac{d}{dx} x^n$, so $$\sum_{n=1}^\infty n x^n = x \frac{d}{dx}\sum_{n=1}^\infty x^n = x \frac{d}{dx} \left(\frac{x}{1-x}\right) = \frac{x}{(1-x)^2}.$$
So we have
$$(1-3x)g(x) = 2 - \frac{4x}{(1-x)^2}$$
which I'm sure you can finish off yourself.
A: 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} 
$$
A: 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$$.
