<s>[INST] Non homogeneous Recurrence relation problem So here i have this non homogeneous recurrence relation i need to solve: 
$$a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n,$$
where $a_{0}=0$, $a_{1}=1$ $a_{2}=98$.  I'm confused at the homogeneous relation part of this relation. What's the characteristic of this type of homogeneous relation? I am planning to solve this like solving a second order recurrence, but is there any simpler way to deal with this?
 [/INST] Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence with no index subtractions:
$$
a_{n + 3}
  = 12 a_{n + 1} + 16 a_n
     + 576 \cdot 4^n + 81 n + 243
$$
The resulting recurrence is now valid for $n \ge 0$ ( no terms for negative index allowed originally).
Multiply by $z^n$, sum over $n \ge 0$, recognize some sums:
\begin{align}
\sum_{n \ge 0} a_{n + r} z^n
  &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{r - 1} z^{r - 1}}{z^r} \\
\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}
and get:
$$
\frac{A(z) - z - 98 z^2}{z^3}
  = 12 \frac{A(z)}{z} + 16 A(z)
     + 576 \frac{1}{1 - 4 z} + 81 \frac{z}{(1 - z)^2} + 243 \frac{1}{1 - z}
$$
Written as partial fractions:
$$
A(z)
  = \frac{1}{(1 - 4 z)^2}
       - \frac{1}{1 - 4 z}
       + \frac{6}{(1 + 2 z)^2}
       + \frac{14}{1 + 2 z}
       - \frac{3}{(1 - z)^2}
       - \frac{5}{1 - z}
$$
Use geometric series and the generalized binomial theorem to read off the coefficients:
$$
\binom{-m}{k} = (-1)^k \binom{m + k - 1}{m - 1}
$$
Note in particular that:
$$
\binom{-2}{n} = (-1)^n (n + 1)
$$
So:
\begin{align}
a_n
  &= (n + 1) \cdot 4^n - 4^n
       + 6 (n + 1) \cdot (-2)^n + 14 \cdot (-2)^n
       - 3 (n + 1) - 5 \\
  &= n \cdot 4^n + (6 n + 20) \cdot (-2)^n - 3 n - 8
\end{align} 
</s>