Solving a first order nonhomogenous recurrence relation

Question

I have the following nonhomogenous recurrence relation:

$a_n = 2 a_{n-1} + 3 a_{n-2} + 8n -4, n \geq 2$

$a_0 = 1, a_1 = 3$

So as you can see, I have a function $f(n) = 8n - 4$ in my relation, which means I have to find a $p_n$ such that $p_n = A p_{n-1} + B p_{n-2} + f(n)$, for $n \geq 3$. After finding $p_n$ I can simply solve the homogeneous recurrence relation. But I have trouble finding $p_n$.

I have tried many things, like for example: $p_n = 8n^2 K_1 - 4K_2 n$, but I end up with complicated equations and I can't find $K_1$ and $K_2$ to determine $p_n$. Or I might not be looking the right way at the equation I end up with.

Answer 1

You should try the function $A+Bn$ for $A,B$ constants and you will obtain the solution $$p_n=-3-2n.$$

Please feel free to show your working if anything goes awry.

Answer 2

$a_n=2a_{n-1}+3a_{n-2}+8n-4$

$a_{n-1}=2a_{n-2}+3a_{n-3}+8(n-1)-4$

Subtract to get

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

$a_{n-1}-a_{n-2}=2a_{n-2}+a_{n-3}-3a_{n-4}+8$

Subtract to get

$a_n-2a_{n-1}+a_{n-2}=2a_{n-1}-a_{n-2}-4a_{n-3}+3a_{n-4}$;

i.e., $a_n=4a_{n-1}-2a_{n-2}-4a_{n-3}+3a_{n-4}$, and now you have a homogenous relation.

Answer 3

With a linear Ansatz,$$a_n = 2 a_{n-1} + 3 a_{n-2} + 8n -4$$ becomes $$pn+q = 2 (pn-p+q) + 3 (pn-2p+q) + 8n -4$$

or

$$p=2p+3p+8,\\q=-2p+2q-6p+3q-4.$$

This system does have a solution.