CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 113
6.7Linear Recurrence Relations with Constant Coefficients
Arecurrence relation of order kis a function of the form
an=(an− 1 ,an− 2 ,...,an−k,n)that is, where thenth termanof a sequence is a function of the precedingktermsan− 1 ,an− 2 ,..., an−k(and
possiblyn). In particular, alinear kth-order recurrence relation with constant coefficientsis a recurrence relation
of the form
an=C 1 an− 1 +C 2 an− 2 +···+Ckan−k+f (n)
whereC 1 ,C 2 ,...,Ckare constants withCk=0, andf (n)is a function ofn. The meanings of the names linear
and constant coefficients follow:
Linear: There are no powers or products of theaj’s.
Constant coefficients: TheC 1 C 2 ,...,Ckare constants (do not depend onn).Iff (n)=0, then the relation is also said to behomogeneous.
Clearly, we can uniquely solve foranif we know the values ofan− 1 ,an− 2 ,...,an−k. Accordingly, by
mathematical induction, there is a unique sequence satisfying the recurrence relation if we are giveninitial values
for the firstkelements of the sequence.
EXAMPLE 6.9 Consider each of the following recurrence relations.
(a) an= 5 an− 1 − 4 an− 2 +n^2
This is a second-order recurrence relation with constant coefficients. It is nonhomogeneous because of then^2.
Suppose we are given the initial conditionsa 1 =1,a 2 =2. Then we can find sequentially the next few
elements of the sequence:
a 3 = 5 ( 2 )− 4 ( 1 )+ 32 = 15 ,a 4 = 5 ( 15 )− 4 ( 2 )+ 42 = 83(b)an= 2 an− 1 an− 2 +n^2
The productan− 1 an− 2 means the recurrence relation is not linear. Given initial conditionsa 1 =1,a 2 =2,
we can still find the next few elements of the sequence:
a 3 = 2 ( 2 )( 1 )+ 32 = 13 ,a 4 = 2 ( 13 )( 2 )+ 42 = 68
(c) an=nan− 1 + 3 an− 2
This is a homogeneous linear second-order recurrence relation but it does not have constant coefficients
because the coefficient ofan− 1 isn, not a constant. Given initial conditionsa 1 =1,a 2 =2, the next few
elements of the sequence follow:
a 3 = 3 ( 2 )+ 3 ( 1 )= 9 ,a 4 = 4 ( 9 )+ 3 ( 2 )= 42
(d)an= 2 an− 1 + 5 an− 2 − 6 an− 3
This is a homogeneous linear third-order recurrence relation with constant coefficients. Thus we need three,
not two, initial conditions to yield a unique solution of the recurrence relation. Suppose we are given the
initial conditionsa 1 =1,a 2 =2,a 3 =1. Then, the next few elements of the sequence follow:a 4 = 2 ( 1 )+ 5 ( 2 )− 6 ( 1 )= 6 ,a 5 = 2 ( 2 )+ 5 ( 1 )− 6 ( 6 )=− 37
a 6 = 2 ( 1 )+ 5 ( 6 )− 6 (− 37 )= 254
This chapter will investigate the solutions of homogeneous linear recurrence relations with constant coeffi-
cients. The theory of nonhomogeneous recurrence relations and recurrence relations without constant coefficients
lies beyond the scope of this text.
For computational convenience, most of our sequences will begin witharather thana. The theory is not
affected at all.