Linear non homogenous recurrences with constant coefficients

Question

When we are guessing the particular solution for a linear non homogenous recurrence with constant coefficients of the form $c_0a_n + c_1a_{n-1} + \cdots+c_na_0 + g(n) =0$ we are asked to guess the particular solution to be as close to $g(n)$ -- a constant multiple of $g(n)$, then linear, quadratic, etc. until the solution is found. Can we always be assured to find a consistent set of coefficients for the guess we make?

Answer 1

No, this does not work even for constant coefficients unless $g(n)$ is of a very special form.

Say, for example.

$$x_{n+1} - x_{n} = \log n$$

You will not find a particular solution using $\log n, n \log n, n^2\log n,$ and so on.