Thread: 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...

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 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