Non homogeneous Recurrence relation problem

Question

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?

Answer 1

It's best to write this with all the $a_k$ terms on one side: $$a_{n}-12a_{n-2}-16a_{n-3}=9\times4^{n}+81n\ .$$ The homogeneous part is $$a_{n}-12a_{n-2}-16a_{n-3}=0\ ,$$ and you solve this exactly as for a second-order recurrence. The only difference is that as this one is third order, your characteristic equation will be cubic instead of quadratic, and therefore possibly harder to solve.

Answer 2

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}