Is every solution of a nonhomogenous linear recurrence also a solution to some homogenous linear recurrence?

Question

In particular, if I have a nonhomogenous linear recurrence of the form $$ a_n = c_1a_{n-1}+c_2a_{n-2} + \ldots + c_ka_{n-k}+p(n), $$ where $p(n)$ is a polynomial, does it follow that every solution to this is also a solution to some non-trivial homogenous linear recurrence?

Answer 1

Yes, it does, at least for a polynomial $p(n)$. It is basically the idea behind the annihilator method $-$ which is more famous for solving differential equations, but nothing prevents you from adapting it to a discrete context such as recurrence relations.

If $La_n = p(n)$ is your recurrence relation, with $L = 1 - (c_1S + \ldots + c_kS^k)$ for instance in your example, where $S$ is the shift operator (acting as $Sa_n = a_{n-1}$), then it is solved by $a_n = b_n + c_n$, where $b_n$ solves the homogeneous problem and $c_n$ is a particular solution to the nonhomogeneous problem. Next, if $A$ is itself a linear operator such that $Ap(n) = 0$, then $AL$ generates the homogeneous linear recurrence relation you are looking for, because $ALa_n = Ap(n) = 0$.

However does such an annihilator $A$ always exist ? For $p(n)$ a polynomial expression of degree $m$, it takes the form $A = (S-1)^{m+1}$, since it is associated to the characteristic polynomial $(r-1)^{m+1}$. Why so ? Because, more generally, multiple roots of the characteristic polynomial produce polynomial prefactors; indeed, the characteristic polynomial $(r-\lambda)^{m+1}$ corresponds to the solution $a_n = (\alpha_0 + \alpha_1n + \ldots + \alpha_mn^m)\lambda^n$.