# recurrence relations - degree of the recurrence

• Apr 6th 2009, 06:50 PM
amyu2005
recurrence relations - degree of the recurrence
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...
• Apr 6th 2009, 08:56 PM
Jhevon
Quote:

Originally Posted by amyu2005
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 :p 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)$