Page 345 - Discrete Mathematics and Its Applications

324 5 / Induction and Recursion

INDUCTIVE STEP: The inductive hypothesis is the statement that P(k) is true, where k is an
arbitrary integer with k ≥ 2; that is, it is the statement that

k k

A j = A j
j = 1 j = 1
whenever A 1 ,A 2 ,...,A k are subsets of the universal set U. To carry out the inductive step,
we need to show that this assumption implies that P(k + 1) is true. That is, we need to show
that if this equality holds for every collection of k subsets of U, then it must also hold for every
collection of k + 1 subsets of U. Suppose that A 1 ,A 2 ,...,A k ,A k+1 are subsets of U. When
the inductive hypothesis is assumed to hold, it follows that

⎛ ⎞
k+1 k

by the definition of intersection
A j ∩ A k+1
A j = ⎝ ⎠
j = 1 j = 1
⎛ ⎞
k

k
A
= ⎝ A j ⎠ ∪ A k+1 by De Morgan’s law (where the two sets are j = 1 j and A k+1 )
j = 1
⎛ ⎞
k

= ⎝ A j ⎠ ∪ A k+1 by the inductive hypothesis
j = 1
k+1

= A j by the definition of union.
j = 1
This completes the inductive step.
Because we have completed both the basis step and the inductive step, by mathematical
induction we know that P (n) is true whenever n is a positive integer, n ≥ 2. That is, we know
that

n n

A j = A j
j = 1 j = 1

whenever A 1 ,A 2 ,...,A n are subsets of a universal set U and n ≥ 2. ▲

PROVING RESULTS ABOUT ALGORITHMS Next, we provide an example (somewhat
more difficult than previous examples) that illustrates one of many ways mathematical induction
is used in the study of algorithms. We will show how mathematical induction can be used to
prove that a greedy algorithm we introduced in Section 3.1 always yields an optimal solution.

EXAMPLE 12 Recall the algorithm for scheduling talks discussed in Example 7 of Section 3.1. The input to
this algorithm is a group of m proposed talks with preset starting and ending times. The goal is
to schedule as many of these lectures as possible in the main lecture hall so that no two talks
overlap. Suppose that talk t j begins at time s j and ends at time e j . (No two lectures can proceed
in the main lecture hall at the same time, but a lecture in this hall can begin at the same time
another one ends.)
Without loss of generality, we assume that the talks are listed in order of nondecreasing
ending time, so that e 1 ≤ e 2 ≤ ··· ≤ e m . The greedy algorithm proceeds by selecting at each
stage a talk with the earliest ending time among all those talks that begin no sooner than when