Page 535 - Discrete Mathematics and Its Applications

514 8 / Advanced Counting Techniques

b) Denote by A ij the product A i A i+1 ..., A j , c) Explain why part (b) leads to the recurrence rela-
and M(i, j) the minimum number of integer mul- tion M(i, j) = min i≤k<j (M(i, k) + M(k + 1,j) +
tiplications required to find A ij . Show that if the m i m k+1 m j+1 ) if 1 ≤ i ≤ j< j ≤ n.
least number of integer multiplications are used to d) Use the recurrence relation in part (c) to construct
compute A ij , where i< j, by splitting the product an efficient algorithm for determining the order
into the product of A i through A k and the product the n matrices should be multiplied to use the min-
of A k+1 through A j , then the first k terms must imum number of integer multiplications. Store the
be parenthesized so that A ik is computed in the partial results M(i, j) as you find them so that your
optimal way using M(i, k) integer multiplications algorithm will not have exponential complexity.
3
and A k+1,j must be parenthesized so that A k+1,j e) Show that your algorithm from part (d) has O(n )
is computed in the optimal way using M(k + 1,j) worst-case complexity in terms of multiplications of
integer multiplications. integers.

8.2 Solving Linear Recurrence Relations

Introduction

A wide variety of recurrence relations occur in models. Some of these recurrence relations can
be solved using iteration or some other ad hoc technique. However, one important class of
recurrence relations can be explicitly solved in a systematic way. These are recurrence relations
that express the terms of a sequence as linear combinations of previous terms.

DEFINITION 1 A linear homogeneous recurrence relation of degree k with constant coefficients is a recur-
rence relation of the form

a n = c 1 a n−1 + c 2 a n−2 + ··· + c k a n−k ,

where c 1 ,c 2 ,...,c k are real numbers, and c k = 0.

The recurrence relation in the definition is linear because the right-hand side is a sum of
previous terms of the sequence each multiplied by a function of n. The recurrence relation is
homogeneous because no terms occur that are not multiples of the a j s. The coefficients of the
terms of the sequence are all constants, rather than functions that depend on n. The degree
is k because a n is expressed in terms of the previous k terms of the sequence.
A consequence of the second principle of mathematical induction is that a sequence satis-
fying the recurrence relation in the definition is uniquely determined by this recurrence relation
and the k initial conditions

a 0 = C 0 ,a 1 = C 1 ,...,a k−1 = C k−1 .

EXAMPLE 1 The recurrence relation P n = (1.11)P n−1 is a linear homogeneous recurrence relation of degree
one. The recurrence relation f n = f n−1 + f n−2 is a linear homogeneous recurrence relation of
degree two. The recurrence relation a n = a n−5 is a linear homogeneous recurrence relation of
degree five. ▲

Example 2 presents some examples of recurrence relations that are not linear homogeneous
recurrence relations with constant coefficients.

EXAMPLE 2 The recurrence relation a n = a n−1 + a 2 is not linear. The recurrence relation H n =
n−2
2H n−1 + 1 is not homogeneous. The recurrence relation B n = nB n−1 does not have constant
coefficients. ▲