Difference equations - second order

Question

How would you find the 'particular solution' to $$x_{n+1}-4x_n+3x_{n-1}=36n^2 $$ I'm unsure of how to deal with this example since if we try a particular solution of the form $cn^2+dn$ then the terms in $n^2$ cancel when we substitute it into the equation. I know that the general solution should be of the form $$x_n=A(3^n)+B +f(n) $$ where $f(n)$ is a polynomial but I can't find $f(n) $ because of the reasons I said above.

Answer 1

The "naive" particular solution to this difference equation would be a generic quadratic function $an^2+bn+c$. But because $1$ is a root of the characteristic polynomial, a quadratic function does not work because quadratic functions get mapped down to linear functions when they are substituted into the left side.

To get around this you can use a cubic function instead; in fact you can be sure that it will be of the form $an^3+bn^2+cn$ (no constant term, as any constant term can be absorbed into the homogeneous solution). You should be able to find details about this in whatever source you are studying from.

A nice linear-algebraic explanation says that if $1$ is a root of the characteristic polynomial of multiplicity $m$, then polynomials of degree at most $m-1$, which is a $m$-dimensional space, are annihilated by the recurrence operator. By the rank-nullity theorem, the image of the polynomials of degree at most $d$, which is a $(d+1)$-dimensional space, is a $(d+1-m)$-dimensional space. So for this image to cover all polynomials of degree at most $d$, you will need to start from polynomials of degree at most $d'$ where $d'+1-m \geq d+1$, so $d'=d+m$ will suffice.