2
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Alex Degtyarev
    Commented Oct 30, 2016 at 22:54
  • $\begingroup$ 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! $\endgroup$
    – James Martin
    Commented Oct 31, 2016 at 9:36

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .