Particular solution of recurrence equations How do we solve recurrence equations of the form:
$$ax_{n+1}+bx_n+cx_{n-1}=dn^p+e\;,$$ where $a,b,c,d,e$ are constants and $p\in \mathbb Z$?
Perhaps we could first solve the homogeneous equation $$ax_{n+1}+bx_n+cx_{n-1}=0\;.$$
Then we find the particular solution... but how? Guesswork?
Thanks.
 A: Guesswork, yes - but, highly educated guesswork. 
If $p$ is a positive integer then there will be a solution in the form of a polynomial of degree $p$, so you write down $x_n=a_0x^p+a_1x^{p-1}+\cdots+a_{p-1}x+a_p$ and substitute it in and work out what $a_0,\dots,a_p$ have to be. 
There is an exception: if the homogeneous equation has a polynomial solution then you have to multiply the guess by $n$ or $n^2$ so it has nothing in common with the solution of the homogeneous equation. 
If $p$ is a negative integer, that's a lot harder. 
A: In fact inhomogeneous linear recurrence equations also have their own versions of 'variation of parameters'.
For second-order inhomogeneous linear recurrence equations, if the inhomogeneous part is $f_n$ and the two linearly independent solutions are $x_n^{(1)}$ and $x_n^{(2)}$ respectively, then the particular solution can be found as $x_n^{(2)}\sum_{k=0}^{n-1}\dfrac{f_kx_{k+1}^{(1)}}{W_{k+1}}-x_n^{(1)}\sum_{k=0}^{n-1}\dfrac{f_kx_{k+1}^{(2)}}{W_{k+1}}$ , where $W_k=\begin{array}{|cc|}x_k^{(1)} & x_k^{(2)}\\x_{k+1}^{(1)} & x_{k+1}^{(2)}\end{array}$ .
See http://faculty.pccu.edu.tw/~meng/Math15.pdf#page=5 for details.
If both $\sum_{k=0}^{n-1}\dfrac{f_kx_{k+1}^{(1)}}{W_{k+1}}$ and $\sum_{k=0}^{n-1}\dfrac{f_kx_{k+1}^{(2)}}{W_{k+1}}$ can eliminate their summation signs, then this particular solution can be extended to use in the version of functional equation.
