Solving a Non-homogeneous Linear Recurrence Relation - how to solve the non-homogeneous component

Question

$ a_{n} = a_{n-1} + 8a_{n-2} - 12a_{n-3} + 25(-3)^{n-2} + 32n^{2} - 64n$ for n $\geq 3$

edit:

I forgot to add the initial conditions, they are $a_0 = 130, a_1 = 215, a_2 = 260$

I have been given the above non-homogeneous linear recurrence relation, however I am struggling to solve the non-homogeneous component of the relation. I understand that I have to split it up into the homogeneous and non-homogeneous terms such that the general solution of the relation has the form:

$a_{n} = b_{n} + p_{n}$

I have solved the homogeneous component of the relation, whose characteristic polynomial is:

$x^3 - x^2 - 8x + 12$

such that the roots are:

$ x = 2 \text{ with multiplicity 2 and } x = -3 $

As such, I have obtained that the solutions to the above homogeneous linear recurrence relations are:

$ b_{n} = C_{1}2^n + C_{2}n(2^{n}) + C_{3}(-3)^{n} $

Now, for the non-homogeneous component:

$ p_{n} = 25(-3)^{n-2} + 32n^{2} - 64n $

I am unsure whether there are any roots of the homogeneous relation that exist in the above equation, since it is my understanding that if that is the case then a particular solution of the non-homogeneous relation can be found in the form:

$ p_{n} = q(n)n^{l}\mu^{n}$

Where q(n) is a polynomial of degree d and $\mu$ is a root of the characteristic polynomial with multiplicity l.

I would appreciate if someone could clarify the steps I would need to take in order to solve the non-homogeneous component of this relation.

Regards

Answer 1

By the superposition principle, you can deal with the non-homogeneous terms separately.

Let us first deal with the polynomial terms. A shifted polynomial is a polynomial of the same degree, so you try a quadratic solution, with undeterminate coefficients. We write

$$an^2+bn+c=a(n-1)^2+b(n-1)+c+8(a(n-2)^2+b(n-2)+c)-12(a(n-3)^2+b(n-3)+c)+32n^2-64n.$$

You can solve the system by developing and identifying the coefficients of the same degree. Another way is by choosing a few values for $n$, say $0,1,2$.

$$\begin{cases}c&=a-b+c+8(4a-2b+c)-12(9a-3b+c),\\ a+b+c&=c+8(a-b+c)-12(4a-2b+c)-32,\\ 4a+2b+c&=a+b+c+8c-12(a-b+c)\end{cases}.$$

Now for the exponential term, the ansatz $a(-3)^n$ will not work, as $-3$ is a root. Instead, try a form $an(-3)^n$.