How to solve 3rd order nonhomogeneous recurrence relation with n in equation? This is a homework question so specifically I am looking for a direction (help). Not an absolute answer.
I understand how to solve 2nd order nonhomogeneous (and I think 3rd order is similiar) recurrence relations. Whats kinking me up with this one is a term with n.
h[n] = 4h[n- 1] - 4h[n-2] + 3n + 1

Here I am using square brackets to indicate subscripts.
Now I can reorganize this equation into:
0 = h[n] - 4h[n-1] + 4h[n-2] -3n-1

From which I can derive the characteristic equation:
0 = x^3 - 4x^2 + 4x - 3n -1

Normally at this point I would solve the roots and be on my way, but here I have that extra n. How do I deal with this?
 A: HINT $\ $ Find a particular polynomial solution $\rm\:h[n]\:$ by undetermined coefficients (notice that the degree can be at most 1).$\ $ The general solution is then the sum of any particular solution and the general solution of the associated homogeneous equation $\rm\ h[n] -4\ h[n-1] + 4\ h[n-2]\ =\ 0\:$.
A: Your 'characteristic equation' doesn't work, as you noted, because of the presence of the variable $n$; it leaves the equation making no sense.  While the particular-solution method works well, there's another general technique that can be used (in principle) to solve recurrence relations that are linear in previous terms and polynomial in $n$: generating functions.  Consider the generating function $H(x) = \sum_{n=0}^{\infty} h[n]x^n$ and use your equation for $h[n]$ to come up with a corresponding equation for $H(x)$. Note that the generating function for $h[n-1]$ is simply $xH(x)$; the 'generating function' for a constant $c$ is $c\over 1-x$, and the generating function for $n$ is $x\over(1-x)^2$ (as can be found by taking the derivative of the generating function for 1 and multiplying by $x$).  Once you come up with a formula you can use it to solve for $H(x)$ and then use the usual partial-fraction methods to turn this back into an explicit formula for $h[n]$.
A: Since presumably the homework was long due, tackle this with generating functions. I'll use proper subscripts in what follows.
Define $H(z) = \sum_{n \ge 0} h_n z^n$. Write the recurrence as:
$$
h_{n + 2} = 4 h_{n + 1} - 4 h_n + 3 n + 7
$$
Multiply by $z^n$, sum over $n \ge 0$, and recognize:
\begin{align}
\sum_{n \ge 0} h_{n + 1} z^n &= \frac{H(z) - h_0}{z} \\
\sum_{n \ge 0} h_{n + 2} z^n &= \frac{H(z) - h_0 - h_1 z}{z^2} \\
\sum_{n \ge 0} z^n           &= \frac{1}{1 - z} \\
\sum_{n \ge 0} n z^n         
   &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\
   &= \frac{z}{(1 - z)^2}                        
\end{align}
to get:
$$
\frac{H(z) - h_0 - h_1 z}{z^2} 
  = 4 \frac{H(z) - h_0}{z} - 4 H(z) + \frac{3 z}{(1 - z)^2} + \frac{7}{1 - z}
$$
Solving for $H(z)$ gives the forbidding expression:
\begin{align}
H(z) 
  &= \frac{h_0 + (h_1 - 6 h_0) z - (2 h_1 - 9 h_0 - 7) z^2 
               + (h_1 - 4 h_0 - 4) z^3}
          {1 - 6 z + 13 z^2 - 12 z^3 + 4 z^4} \\
  &= \frac{10}{1 - z}
       + \frac{3}{(1 - z)^2}
       - \frac{h_1 - 4 h_0 + 36}{2 (1 - 2 z)}
       + \frac{h_1 - 2 h_0 + 10}{2 (1 - 2 z)^2}
\end{align}
Using the generalized binomial theorem and geometric series, this tells us the coefficients:
\begin{align}
h_n &= 10 + 3 \cdot (-1)^n \binom{-2}{n}
          - \frac{h_1 - 4 h_0 + 36}{2} \cdot 2^n
          + \frac{h_1 - 2 h_0 + 10}{2} \cdot \binom{-2}{n} (-2)^n 
\end{align}
As $(-1)^n \binom{-2}{n} = n + 1$, this reduces to:
$$
h_n = \frac{1}{2} \left(
                    (h_1 - 2 h_0 + 10) n + 2 h_0 - 26) 2^n  + 6 n + 26
                  \right)
$$
The algebra help from maxima is gratefully acknowledged.
