recurrence relations - degree of the recurrence

amyu2005 · #1 $Old$ April 6th, 2009, 06:50 PM

I have a recurrence:

an = an-1 + an-2 + 2n-3

is this a degree of 2 or 3?

b/c if it's 2 I get r2 – r – 1 & there are no integer roots....

but if it's degree 3, it would be r^3 - r^2 - r - 2 & I don't know how to find the roots of a degree 3 function...

Jhevon · #2 $Old$ April 6th, 2009, 08:56 PM

Quote:

Originally Posted by amyu2005 $View Post$

I have a recurrence:

an = an-1 + an-2 + 2n-3

is this a degree of 2 or 3?

b/c if it's 2 I get r2 – r – 1 & there are no integer roots....

but if it's degree 3, it would be r^3 - r^2 - r - 2 & I don't know how to find the roots of a degree 3 function...

don't know much about difference equations

but assuming your cubic is correct, we apply the rational roots theorem and see that r = 2 is a root. and so (r - 2) is a factor. after factoring this out, with the aid of polynomial long division, or synthetic division, or your favorite method, we get $(r - 2)(r^2 + r + 1)$