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

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?

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$$.
• Thank you. I can see that it works, and I think I to an extent understand why it does, but I'm having a bit of a hard time seeing why exactly the annihilator takes the form $(S-1)^{m+1}$. Nov 21 at 9:30