Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $
This is a practice question I'm working on, and I'm running into absurd amounts of calculations with everything I have tried. I would really appreciate some guidance on this question, as I get the feeling there must be an easier way, or short cut to this question somewhere.
I've tried using both generating functions and the usual method of solving non-homogeneous recurrence relations.
The first method with generating functions, I let 
$$A(z) = \sum^{\infty}_{n=0} a_{n}z^n$$ be a generating function. Putting in the initial conditions, I get:
$$ A(z) = 23 + 37z + 42z^2 + \sum^{\infty}_{n=3} (12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n)z^n$$
after a bunch of simplifying and expressing the RHS in terms of $A(z)$, I get:
$$A(z) =  23 + 37z + 42z^2 + 12z^2(A(z)-23) - 16z^3A(Z)+ \frac{6}{1-2z}+25(\frac{z}{(1-z)^2} - z- 2z^2)$$
After rearranging and moving the $A(z)$ terms to the other side, I get:
$$A(z) = \frac{29-67z+23z^2+14z^3-24z^4}{(2z-1)^2(4z+1)(1-2z)(1-z)^2} $$
which turns into an absolutely hideous partial fraction decomposition, trying to solve for 6 constants. I pretty much went as far as I could go with it and still ran into a dead end, so i decided to try the usual method.
Doing the usual method, I try to solve the homogeneous part first, which is reasonably easy. My characteristic polynomial is $x^3-12x+16=0$, giving me roots $\lambda = 2 $(of multiplicity 2) and $\lambda = -4 $
So my solution to the homogeneous part is:
$$b_n = C_12^n+C_2n2^n+C_3(-4)^n$$
Now to get a particular solution, I try: $p_n = C_4n^2\cdot 6 \cdot 2^n + C_5n$
$$ \implies C_4n^2\cdot 6 \cdot 2^n + C_5n = 12(C_4(n-2)^2\cdot 6 \cdot 2^{(n-2)} + C_5(n-2)) - 16(C_4(n-3)^2\cdot 6 \cdot 2^{(n-3)} + C_5(n-3)) + 6\cdot2^n+25n $$
Another pretty nasty algebraic exercise (although not quite as bad as the generating function). However, I persist and after expanding the terms, I try to collect the $n^2\cdot2^n$ and $n$ terms together - to try and solve a simultaneous equation, but I run into the problem that I get terms without $n^2\cdot2^n$ nor $n$ and then some terms with $n\cdot 2^{n}$.
Would greatly appreciate some help with this practice question! Many thanks in advance.

Simplest way I know: Define the generating function:
$$
G(z) = \sum_{n \ge 0} g_n z^n
$$
Write the recurrence without subtraction in indices:
$$
g_{n + 3}
  = 12 g_{n + 1} - 16 g_n + 48 \cdot 2^n + 25 n + 75
$$
If you multiply by $z^n$, sum over $n \ge 0$, and recognize the resulting sums:
\begin{align}
\sum_{n \ge 0} g_{n + k} z^k
  &= \frac{G(z) - g_0 - g_1 z - \ldots - z_{k - 1} z^{k - 1}}{z^k} \\
\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{G(z) - 23 - 37 z - 42 z^2}{z^3}
  = 12 \frac{G(z) - 23}{z} - 16 G(z)
     + 48 \frac{1}{1 - 2 z}
     + 25 \frac{z}{(1 - z)^2}
     + 75 \frac{1}{1 - z}
$$
This gives the formidable:
\begin{align}
G(z)
  &= \frac{23 - 55 z - 267 z^2 + 1198 z^3 - 1540 z^4 + 612 z^5}
          {1 - 4 z + 7 z^2 - 62 z^3 + 124 z^4 - 104 z^5 + 32 z^6} \\
  &= \frac{19}{1 - z}
       + \frac{5}{(1 - z)^2}
       - \frac{2}{(1 - 2 z)^2}
       + \frac{2}{(1 - 2 z)^3}
       - \frac{1}{1 + 4 z}
\end{align}
Using the generalized binomial theorem,
in particular for natural $m$:
$$
(1 - u)^{-m}
  = \sum_{k \ge 0} \binom{m + k - 1}{m - 1} u^k
$$
and the expansion as polynomials of the binomial coefficients:
\begin{align}
g_n
  &= 19 
      + 5 \binom{n + 2 - 1}{2 - 1}
      - 2 \binom{n + 2 - 1}{2 - 1} \cdot 2^n
      + 2 \binom{n + 3 - 1}{3 - 1} \cdot 2^n
      - 4^n \\
  &= 24 + 5 n + (n^2 + n) \cdot 2^n - 4^n
\end{align}
The algebra help by maxima is gratefully aknowledged.
