3
$\begingroup$

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.

  • 0
    This question has been solved perfectly. Hope that the asker has been diving enough and accept the answer at an early date.2012-09-10

2 Answers 2

2

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.

0

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.