Solving a non-homogeneous recurrence relation

Question

I have the following non-linear homogeneous recurrence relation:

$a_n = 6a_{n-1} - 12a_{n-2} + 8a_{n-3} + 2^n$

And I need to solve it by giving a general form . So I get the process. First I solve $a_n = 6a_{n-1} - 12 a_{n-2} + 8a_{n-3}$, and then I find a particular solution to the whole by "guessing" its general form and then finding the coefficients.

I'm fine with the first part, but I don't know what I should be guessing for the particular solution. I am told that I should guess something similar to teh non-linear term, I tried guessing $a_n = 2^n$ but that didn't work, so then I figured maybe $a_n = (c_3 n^3 + c_2 n^2 + c_1 n + c_0) 2^n$ and I got an answer of $c_3 = \frac{1}{6}$ and $c_2, c_1 c_0$ could be anything since the coefficients cancel, which I don't think is right (or, at least when I substitute this back, I get weird answers).

Can anyone advise me on how I should "guess"?

---

Extra detail on the solution I have so far

First I solve $a_n = 6a_{n-1} - 12 a_{n-2} + 8a_{n-3}$.

I suppose $a_n = r^n$, then we get $(r-2)^3 = 0$ so the solution is of the form $a_n (c_2 n^2 + c_1 n + c_0) 2^n$

Now I find a particular solution to $a_n = 6a_{n-1} - 12 a_{n-2} + 8a_{n-3} + 2^n$. I'm stuck here because I don't know how I should "guess" the form of $a_n$.

Answer 1

Write:

$$ a_{n + 3} = 6 a_{n + 2} - 12 a_{n + 1} + 8 a_n + 8 \cdot 2^n $$

Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$, multiṕly by $z^n$, sum over $n \ge 0$ and recognize some sums to get:

$$ \frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} = 6 \frac{A(z) - a_0 - a_1 z}{z^2} - 12 \frac{A(z) - a_0}{z} + 8 A(z) + 8 \frac{1}{1 - 2 z} $$

Solving for $A(z)$ gives:

$\begin{align} A(z) &= \frac{a_0 + (a_2 + a_1 - 8 a_0) z - (2 a_2 + 8 a_1 - 24 a_0) z^2 + (12 a_1 - 24 a_0 + 8) z^3} {1 - 8 z + 24 z^2 - 32 z^3 + 16 z^4} \\ &= \frac{a_0 + (a_2 + a_1 - 8 a_0) z - (2 a_2 + 8 a_1 - 24 a_0) z^2 + (12 a_1 - 24 a_0 + 8) z^3} {(1 - 2 z) (1 - 6 z + 12 z^2 - 8 z^3)} \\ &= \frac{a_0 + (a_2 + a_1 - 8 a_0) z - (2 a_2 + 8 a_1 - 24 a_0) z^2 + (12 a_1 - 24 a_0 + 8) z^3} {(1 - 2 z) (1 - 6 z + 12 z^2 - 8 z^3)} \\ &= \frac{a_0 + (a_2 + a_1 - 8 a_0) z - (2 a_2 + 8 a_1 - 24 a_0) z^2 + (12 a_1 - 24 a_0 + 8) z^3} {(1 - 2 z)^4} \end{align}$

Note the factors of the next-to-last denominator, compare to the recurrence.

This can be split into partial fractions, giving something like:

$$ A(z) = \frac{\alpha}{(1 - 2 z)^4} + \frac{\beta}{(1 - 2 z)^3} + \frac{\gamma}{(1 - 2 z)^2} + \frac{\delta}{1 - 2 z} $$

Now we know that:

$\begin{align} (1 - r z)^{-k} &= \sum_{n \ge 0} (-1)^n \binom{-k}{n} r^n z^n \\ &= \sum_{n \ge 0} \binom{n + k + 1}{k - 1} r^n z^n \end{align}$

Now $\binom{n + k - 1}{k - 1}$ is a polynomial of degree $k - 1$ in $n$, so the final solution (the coefficient of $z^n$ in $A(z))$ is of the form:

$$ a_n = (\alpha_3 n^3 + \alpha_2 n^2 + \alpha_1 n + \alpha_0) \cdot 2^n $$

A tame computer algebra system will give the constants explicitly in terms of the initial values, but that is way overkill. The same steps can be traced with specific values, giving the solution directly.

Note added later: In any case, knowing the form of the solution allows you to set up a system of equations for the $\alpha_i$ using the initial values. That should be simpler than tracing them through the whole mess.