Page 362 - Discrete Mathematics and Its Applications

5.2 Strong Induction and Well-Ordering 341

showed that the principle of mathematical induction follows from the well-ordering property.
The other parts of this equivalence are left as Exercises 31, 42, and 43.

THE WELL-ORDERING PROPERTY Every nonempty set of nonnegative integers has a
least element.
The well-ordering property can often be used directly in proofs.

EXAMPLE 5 Use the well-ordering property to prove the division algorithm. Recall that the division algorithm
states that if a is an integer and d is a positive integer, then there are unique integers q and r
with 0 ≤ r< d and a = dq + r.

Solution: Let S be the set of nonnegative integers of the form a − dq, where q is an integer. This
set is nonempty because −dq can be made as large as desired (taking q to be a negative integer
with large absolute value). By the well-ordering property, S has a least element r = a − dq .
0
The integer r is nonnegative. It is also the case that r< d. If it were not, then there would
be a smaller nonnegative element in S, namely, a − d(q 0 + 1). To see this, suppose that r ≥ d.
Because a = dq + r, it follows that a − d(q 0 + 1) = (a − dq ) − d = r − d ≥ 0. Conse-
0
0
quently, there are integers q and r with 0 ≤ r< d. The proof that q and r are unique is left as
Exercise 37. ▲

EXAMPLE 6 In a round-robin tournament every player plays every other player exactly once and each match
has a winner and a loser. We say that the players p 1 ,p 2 ,...,p m form a cycle if p 1 beats p 2 , p 2
beats p 3 ,...,p m−1 beats p m , and p m beats p 1 . Use the well-ordering principle to show that if
there is a cycle of length m(m ≥ 3) among the players in a round-robin tournament, there must
be a cycle of three of these players.

Solution: We assume that there is no cycle of three players. Because there is at least one cycle
in the round-robin tournament, the set of all positive integers n for which there is a cycle of
length n is nonempty. By the well-ordering property, this set of positive integers has a least
element k, which by assumption must be greater than three. Consequently, there exists a cycle
of players p 1 ,p 2 ,p 3 ,...,p k and no shorter cycle exists.
Because there is no cycle of three players, we know that k> 3. Consider the first three
elements of this cycle, p 1 , p 2 , and p 3 . There are two possible outcomes of the match between
p 1 and p 3 .If p 3 beats p 1 , it follows that p 1 , p 2 , p 3 is a cycle of length three, contradicting
our assumption that there is no cycle of three players. Consequently, it must be the case that
p 1 beats p 3 . This means that we can omit p 2 from the cycle p 1 ,p 2 ,p 3 ,...,p k to obtain the
cycle p 1 ,p 3 ,p 4 ,...,p k of length k − 1, contradicting the assumption that the smallest cycle
has length k. We conclude that there must be a cycle of length three. ▲

Exercises

1. Use strong induction to show that if you can run one mile parts of this exercise outline a strong induction proof that
or two miles, and if you can always run two more miles P(n) is true for n ≥ 8.
once you have run a specified number of miles, then you a) Show that the statements P(8), P(9), and P(10) are
can run any number of miles. true, completing the basis step of the proof.
2. Use strong induction to show that all dominoes fall in an b) What is the inductive hypothesis of the proof?
infinite arrangement of dominoes if you know that the c) What do you need to prove in the inductive step?
first three dominoes fall, and that when a domino falls, d) Complete the inductive step for k ≥ 10.
the domino three farther down in the arrangement also e) Explain why these steps show that this statement is
falls. true whenever n ≥ 8.
3. Let P(n) be the statement that a postage of n cents can be 4. Let P(n) be the statement that a postage of n cents can be
formed using just 3-cent stamps and 5-cent stamps. The formed using just 4-cent stamps and 7-cent stamps. The