# 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.

-
You can find the particular solution using generating functions. This is closely analogous to using the Laplace transform to find a particular solution to an ODE. –  Qiaochu Yuan Dec 30 '11 at 3:54
This question has been solved perfectly. Hope that the asker has been diving enough and accept the answer at an early date. –  doraemonpaul Sep 10 '12 at 1:38

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.

-

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.

-