2

Suppose we have a non-homogeneous linear recurrence relation $$ a(n) + c_{1}a(n-1) + \dots + c_{d}a(n-d) = p(n), \,\, n\in\mathbb{Z} $$ where $c_1,\dots, c_d$ are constants. If $p(n)$ is a polynomial, is there always a particular solution $a(n)$ which is a polynomial?

Basic texts I've looked at are all following a trial-and-error approach, without stating anything general. A pointer to a helpful reference would be much appreciated!

James Martin
  • 801
  • Yes; check any textbook in discrete math. You can find a solution by indetermined coefficients as a polynomial of degree $\deg p$ plus the multiplicity of $0$ as a root of the characteristic equation. All the theory is exactly the same as in the case of differential equations. –  Oct 30 '16 at 22:54
  • Thanks for your comment! The thing is, a large proportion of the basic texts actually don't do this. The "method of indetermined coefficients" is even given another colloquial name: "method of judicious guessing"! And the presentation is something like: here's what you should guess in this kind of case; look, here are some examples where it works. If you have a nice suggestion of a particular textbook where this result is stated in a nice way, that would be fab! – James Martin Oct 31 '16 at 09:36

1 Answers1

0

As noted above, there are many resources for this well-studied problem. In particular, when the the RHS is a polynomial of degree $k$ you start with the ansatz $Q(x)$ of the same degree. There are also algorithms. At any rate, here is one online reference in case you find no access to books. http://www.fq.math.ca/Scanned/40-2/el-wahbi.pdf

T. Amdeberhan
  • 327