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

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

is given by

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

I've done this so far:

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

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

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

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

But I'm stuck now on getting those powers back to $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

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

is given by

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

I've done this so far:

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

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

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

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

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

So your characteristic (or whatever) is
$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
$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:

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

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

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

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

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

-Dan