<s>[INST] 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?
 [/INST] 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.
</s>