<s>[INST] non-homogeneous recurrence relations The question is:
$a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n$with $a_{0}=0 ,a_{1}=1 ,a_{2}=98$
I tried to deal with the particular solution first by:
$A4^{n}+Bn=12[A4^{n-2}+B(n-2)]+16[A4^{n-3}+B(n-3)]+9\cdot 4^{n}+81n$.
However, turns out the coefficient of $4^{n}$being 0 which means 9=0 which is clearly wrong.
Could anyone please show me where did I do wrong in the working? Many thanks.
 [/INST] Go for generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, rewrite the recurrence without index subtractions:
$$
a_{n + 3} = 12 a_{n + 1} + 16 a_n + 576 \cdot 4^n + 81 n + 243
$$
Multiply by $z^n$, sum over $n \ge 0$, and recognize a few sums to get:
$$
\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3}
  = 12 \frac{A(z) - a_0}{z} + 16 A(z)
      + 576 \frac{1}{1 - 4 z}
      + 81 \frac{z}{(1 - z)^2}
      + 243 \frac{1}{1 - z}
$$
This gives the formidable:
\begin{align}
A(z)
  &= \frac{z + 92 z^2 + 240 z^3 - 1408 z^4 + 832 z^5}
          {1 - 6 z - 3 z^2 + 52 z^3 - 12 z^4 - 96 z^5 + 64 z^6} \\
  &= \frac{14}{1 + 2 z} - \frac{6}{(1 + 2 z)^2}
       - \frac{5}{1 - z}
       + \frac{3}{(1 - z)^3}
       - \frac{4}{1 - 4 z}
       + \frac{4}{(1 - 4 z)^2}
\end{align}
Geometric series and the generalized binomial theorem, in particular:
$$
\binom{-m}{k} = (-1)^k \binom{m + k - 1}{m - 1}
$$
finish this off:
\begin{align}
a_n
  &= 14 \cdot (-2)^n
      - 6 \cdot \binom{n + 1}{2} \cdot (-2)^n
      - 5
      + 3 \cdot \binom{n + 2}{2}
      - 4 \cdot 4^n
      + 4 \cdot \binom{n + 1}{1} \cdot 4^n \\
  &= (8 - 6 n) \cdot (-2)^n
      + \frac{2 n^2 + 9 n - 4}{2}
      + n \cdot 4^{n + 1}
\end{align}
</s>