Page 354 - Discrete Mathematics and Its Applications

5.2 Strong Induction and Well-Ordering 333

the set of real numbers x with a< x < b, where a and b person throws a pie at their nearest neighbor, it is possible
are real numbers with a< b.) that everyone is hit by a pie.
Sometimes we cannot use mathematical induction to prove 76. Construct a tiling using right triominoes of the 4 × 4
a result we believe to be true, but we can use mathematical checkerboard with the square in the upper left corner re-
induction to prove a stronger result. Because the inductive hy- moved.
pothesis of the stronger result provides more to work with, this 77. Construct a tiling using right triominoes of the 8 × 8
process is called inductive loading. We use inductive loading checkerboard with the square in the upper left corner re-
in Exercise 74. moved.
78. Prove or disprove that all checkerboards of these shapes
74. Suppose that we want to prove that
can be completely covered using right triominoes when-
ever n is a positive integer.
1 3 2n − 1 1
· ··· < √ a) 3 × 2 n b) 6 × 2 n
2 4 2n 3n
n
n
c) 3 × 3 n d) 6 × 6 n
for all positive integers n. ∗ 79. Show that a three-dimensional 2 × 2 × 2 checker-
n
n
n
a) Show that if we try to prove this inequality using math- board with one 1 × 1 × 1 cube missing can be completely
ematical induction, the basis step works, but the in- covered by 2 × 2 × 2 cubes with one 1 × 1 × 1 cube re-
ductive step fails. moved.
∗ 80. Show that an n × n checkerboard with one square re-
b) Show that mathematical induction can be used to moved can be completely covered using right triominoes
prove the stronger inequality if n> 5, n is odd, and 3 | n.
1 3 2n − 1 1 81. Show that a 5 × 5 checkerboard with a corner square re-
· ··· < √ moved can be tiled using right triominoes.
2 4 2n 3n + 1
∗ 82. Find a 5 × 5 checkerboard with a square removed that
for all integers greater than 1, which, together with a cannot be tiled using right triominoes. Prove that such a
verification for the case where n = 1, establishes the tiling does not exist for this board.
weaker inequality we originally tried to prove using 83. Use the principle of mathematical induction to show that
mathematical induction. P(n) is true for n = b, b + 1,b + 2,..., where b is an
75. Let n be an even positive integer. Show that when n peo- integer, if P(b) is true and the conditional statement
ple stand in a yard at mutually distinct distances and each P(k) → P(k + 1) is true for all integers k with k ≥ b.

5.2 Strong Induction and Well-Ordering

Introduction

In Section 5.1 we introduced mathematical induction and we showed how to use it to prove a
variety of theorems. In this section we will introduce another form of mathematical induction,
called strong induction, which can often be used when we cannot easily prove a result using
mathematical induction. The basis step of a proof by strong induction is the same as a proof of
the same result using mathematical induction. That is, in a strong induction proof that P (n) is
true for all positive integers n, the basis step shows that P(1) is true. However, the inductive steps
in these two proof methods are different. In a proof by mathematical induction, the inductive
step shows that if the inductive hypothesis P(k) is true, then P(k + 1) is also true. In a proof
by strong induction, the inductive step shows that if P(j) is true for all positive integers not
exceeding k, then P(k + 1) is true. That is, for the inductive hypothesis we assume that P(j)
is true for j = 1, 2,...,k.
The validity of both mathematical induction and strong induction follow from the well-
ordering property in Appendix 1. In fact, mathematical induction, strong induction, and well-
ordering are all equivalent principles (as shown in Exercises 41, 42, and 43). That is, the validity
of each can be proved from either of the other two. This means that a proof using one of these
two principles can be rewritten as a proof using either of the other two principles. Just as it is
sometimes the case that it is much easier to see how to prove a result using strong induction
rather than mathematical induction, it is sometimes easier to use well-ordering than one of the