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.
 A: I started your problem from scratch and arrived to something different (I have not been able to find where there has been a difference). First, I arrived to $$A(z)=\frac{-616 z^5+1540 z^4-1198 z^3+267 z^2+55 z-23}{(z-1)^2 (2 z-1)^3 (4 z+1)}$$ which decomposes as $$A(z)=-\frac{19}{z-1}-\frac{2}{(1-2 z)^2}+\frac{5}{(z-1)^2}-\frac{2}{(2 z-1)^3}-\frac{1}{4
   z+1}$$ Reworking from here, I arrived to quite messy expressions for $g_n$ which, fortunately, simplify to $$g_n=2^n (n+1) n+5 n-(-4)^n+24$$
A: The characteristic polynomial $\lambda^3-12\lambda +16$ of the corresponding homogeneous difference equation
$$h_n-12 h_{n-2}+16 h_{n-3}=0\tag{1}$$
has $2$, $2$, $-4$ as  roots. The general solution of $(1)$ is therefore given by
$$h_n=(A+Bn) 2^n+ C(-4)^n$$
with arbitrary $A$, $B$, $C$.
On the right hand side of the given difference equation
$$g_n-12 g_{n-2}+16 g_{n-3}=6\cdot 2^n+25n\tag{2}$$
we see a linear combination of a solution of $(1)$ belonging to the eigenvalue $2$ of multiplicity $2$,  and a polynomial of degree $1$. For a particular solution $n\to p_n$ of $(2)$ we therefore make the "Ansatz"
$$p_n:= D\, n^2\>2^n + (E + F n)$$
and now have to determine $D$, $E$, $F$ such that $(2)$ is satisfied identically in $n$. Solving the resulting system of linear equations gives
$$p_n= n^2\>2^n+24+5 n\ .$$
The general solution of $(2)$ is therefore given by
$$g_n=h_n+p_n=\left(A+Bn+ n^2\right)2^n + C(-4)^n+24+5n\qquad(n\in{\mathbb Z})\ .$$
Finally the constants $A$, $B$, $C$ have to be determined by the initial condtions. One obtains $A=0$, $B=1$, $C=-1$, so that we have the following end result:
$$g_n=(n+n^2)\>2^n-(-4)^n+24+5n\ .$$
A: 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.
A: For a homogeneous linear recurrence $A_n = c_1A_{n-1} + ... + c_kA_{n-k}$ call let $P_A(x)= x^k - c_1x^{k-1} -... -c_k$ be it's characteristic polynomial. The main theorem about these is that for any choice of initial values for $A_0, A_1, ... ,A_k$ we can write a unique closed form for $A_n$ as a linear combination of terms of the form $n^l\lambda^n$ where $\lambda$ is a root of$P_A(x)$ of multiplicity greater than $l$. Moreover any sequence of that form will satisfy the same recursion.
Now suppose we have a non-homogeneous recurrence of the form $A'_n = c_1A'_{n-1} + ... + c_kA'_{n-k} + B_n$, where $B_n$ satisfies a homogeneous linear recurrence with characteristic polynomial $P_B(x)$. The main result here is that $A'_n$ also satisfies a homogeneous recurrence relation, and in fact it satisfies the recurrence relation with characteristic polynomial $P_{A'}(x)=P_A(x)P_B(x)$.
So in light of these two results I can look at your question and know right away that it must have a closed form of the form $A_n= a_1 + a_2n + a_32^n + a_4n2^n + a_5n^22^n+a_6(-4)^n$ and from there solving for the coefficients is easy given the first few terms.
