State whether or not each recurrence relation below is a lin

State whether or not each recurrence relation below is a linear homogeneous recurrence relation with constant coefficients. • If so, give the order of the recurrence relation. • If not, indicate why not.

(a) an = 3nan1 + an2

(b) an = 4an3

(c) an = an1 + 1

Solution

a) a_n=3na_n-1+a_n-2 is not a linear homogeneous recurrence relation with constant coefficients. Because the coefficient of a_n-1 is 3n which is not a constant.

b) a_n= 4a_n-3 is a linear homogeneous recurrence relation with constant coefficient, and order is 3.

c) a_n=a_n-1+1 is not a linear homogeneous recurrence relation with constant coefficients, it is linear but not homogeneous.