# Thread: General solution to 3rd order recurrence relation

1. ## General solution to 3rd order recurrence relation

Hi, I'm a bit stuck on this question:

For a fixed r, show that the general solution to the recurrence relation

$\displaystyle x_{n} = rx_{n-1} + r^2x_{n-2} - r^3x_{n-3}$

is given by

$\displaystyle x_{n} = Ar^n + Bnr^n + C(-r)^n$ for constants $\displaystyle A, B, C \in \mathbb{R}$

I've done this so far:

Let $\displaystyle x_{n-1} = a^n$

$\displaystyle a^n = ra^{n-1} +r^2na^{n-2} -r^3xa^{n-3}$

Divide through by $\displaystyle a^{n-3}$

$\displaystyle a^3 = ra^2 + r^2na - r^3$

But I'm stuck now on getting those powers back to $\displaystyle n$. Any pointers most welcome!

2. Originally Posted by Salome
Hi, I'm a bit stuck on this question:

For a fixed r, show that the general solution to the recurrence relation

$\displaystyle x_{n} = rx_{n-1} + r^2x_{n-2} - r^3x_{n-3}$

is given by

$\displaystyle x_{n} = Ar^n + Bnr^n + C(-r)^n$ for constants $\displaystyle A, B, C \in \mathbb{R}$

I've done this so far:

Let $\displaystyle x_{n-1} = a^n$

$\displaystyle a^n = ra^{n-1} +r^2na^{n-2} -r^3xa^{n-3}$

Divide through by $\displaystyle a^{n-3}$

$\displaystyle a^3 = ra^2 + r^2na - r^3$

But I'm stuck now on getting those powers back to $\displaystyle n$. Any pointers most welcome!
Not quite sure where you got your, what is it called, a characteristic equation? Anyway, rewrite your recursion as
$\displaystyle x_{n + 3} - rx_{n + 2} - r^2x_{n + 1} + r^3x_n = 0$

So your characteristic (or whatever) is
$\displaystyle y^3 - ry^2 - r^2y + r^3 = 0$

You can guess that y = r is a solution (use a variant on the rational root theorem. Possible roots in terms of r are y = (+/-) (1, r, r^2, r^3). )

So eventually we can show that
$\displaystyle y^3 - ry^2 - r^2y + r^3 = (y - r)^2(y + r) = 0$

Can you go from there?

-Dan

3. Gotcha, thanks so much! Though I think here:

$\displaystyle y^2 - ry^2 - r^2y + r^3 = (y - r)^2(y + r) = 0$

the first $\displaystyle y^2$ should be $\displaystyle y^3$?

4. Originally Posted by Salome
Gotcha, thanks so much! Though I think here:

$\displaystyle y^2 - ry^2 - r^2y + r^3 = (y - r)^2(y + r) = 0$

the first $\displaystyle y^2$ should be $\displaystyle y^3$?
Yes, I have fixed that in my original post. Thanks for the catch!

-Dan