Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.