Page 335 - Discrete Mathematics and Its Applications

314 5 / Induction and Recursion

FIGURE 2 Illustrating How Mathematical Induction Works Using Dominoes.

WAYS TO REMEMBER HOW MATHEMATICAL INDUCTION WORKS Thinking of
the infinite ladder and the rules for reaching steps can help you remember how mathematical
induction works. Note that statements (1) and (2) for the infinite ladder are exactly the basis
step and inductive step, respectively, of the proof that P (n) is true for all positive integers n,
where P (n) is the statement that we can reach the nth rung of the ladder. Consequently, we can
invoke mathematical induction to conclude that we can reach every rung.
Another way to illustrate the principle of mathematical induction is to consider an infinite
row of dominoes, labeled 1, 2, 3,...,n,... , where each domino is standing up. Let P (n) be
the proposition that domino n is knocked over. If the first domino is knocked over—i.e., if P(1)
is true—and if, whenever the kth domino is knocked over, it also knocks the (k + 1)st domino
over—i.e., if P(k) → P(k + 1) is true for all positive integers k—then all the dominoes are
knocked over. This is illustrated in Figure 2.

Why Mathematical Induction is Valid

Why is mathematical induction a valid proof technique? The reason comes from the well-
ordering property, listed in Appendix 1, as an axiom for the set of positive integers, which
states that every nonempty subset of the set of positive integers has a least element. So, suppose
we know that P(1) is true and that the proposition P(k) → P(k + 1) is true for all positive
integers k. To show that P (n) must be true for all positive integers n, assume that there is at
least one positive integer for which P (n) is false. Then the set S of positive integers for which
P(n) is false is nonempty. Thus, by the well-ordering property, S has a least element, which
will be denoted by m. We know that m cannot be 1, because P(1) is true. Because m is positive
and greater than 1, m − 1 is a positive integer. Furthermore, because m − 1 is less than m,itis
not in S,so P(m − 1) must be true. Because the conditional statement P(m − 1) → P(m) is
also true, it must be the case that P(m) is true. This contradicts the choice of m. Hence, P(n)
must be true for every positive integer n.

The Good and the Bad of Mathematical Induction

An important point needs to be made about mathematical induction before we commence a
study of its use. The good thing about mathematical induction is that it can be used to prove