non-homogeneous recurrence relations

Question

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.

Answer 1

Oh it's a 'trick' question. Note that the characteristic polynomial of the corresponding homogenous recurrence is $r \mapsto r^3-12r-16$ which has $4$ as a root, and hence when you substituted $4^n$ in it didn't work.

In general we can solve all such recurrences by repeatedly applying the operator

  $f(n) \mapsto f(n+1) - r f(n)$

for some $r$ until it becomes homogenous. In this case to get rid of the $4^n$ term we use $f(n) \mapsto f(n+1) - 4 f(n)$ and to get rid of the linear term we use $f(n) \mapsto f(n+1) - f(n)$ twice. If you understand the proof of the general solution for the homogenous case, then you will immediately see how those 'non-homogenous' terms interact with the homogenous solution, because they will now show up in the factors of the characteristic polynomial together with those from the homogenous case. In this case we will get roots -2,-2,4,4,1,1, which corresponds to the general solution $a_n = (An+B)(-2)^n + (Cn+D)4^n + (En+F)$.

Answer 2

I see user21820 has given a good answer while I went AFK, but I figured I'd share this anyway since I worked it out...

We can apply the method of annihilators to convert this into a 6th order, constant coefficient, homogeneous recurrence. For background on the method of annihilators, see these links.

First, we rewrite and reindex the recurrence: $$a_n = 12a_{n-2} + 16_{n-3} + 9\cdot 4^n + 81n \implies a_{n+3}-12a_{n+1}-16a_n = 9\cdot 4^{n+3}+81(n+3)$$

Next, we rewrite using the shift operator (and I've simplified some of the products): $$(E^3-12E-16)\langle a_n\rangle = \langle 576\cdot 4^n\rangle +\langle 81n \rangle + \langle 243 \rangle$$

Note that the annihilator for $4^n$ is $(E-4)$, the annihilator for $n$ is $(E-1)^2$, and the annihilator for $243$ is $(E-1)$. We apply the annihilators to the whole equation: $$\begin{align}(E-4)(E-1)^2(E^3-12E-16)\langle a_n\rangle = &(E-4)(E-1)^2\langle 576\cdot 4^n\rangle \\&+(E-4)(E-1)^2\langle 81n \rangle \\&+ (E-4)(E-1)^2\langle 243 \rangle\end{align}$$

The RHS is annihilated, so: $$(E-4)(E-1)^2(E^3-12E-16)\langle a_n\rangle = \langle 0\rangle$$

Factoring the annihilators (which gives the roots of the characteristic), we find this is equivalent to: $$(E-4)^2(E-1)^2(E+2)^2\langle a_n\rangle = \langle 0\rangle$$

We have 3 roots, each of of multiplicity $2$. So: $$a_n = c_14^n + c_2n4^n + c_31^n + c_4n1^n + c_5(-2)^n + c_6n(-2)^n$$ Or, simplified: $$a_n = 4^n(c_1 + nc_2) + (c_3 + nc_4) + (-2)^n(c_5 + nc_6)$$

Computing the first 6 terms of the sequence provides 6 linear equations in 6 unknowns, which can be (relatively) easily solved.

(And my answer matches the other one, which is a good sign...) :)

Answer 3

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}