Page 356 - Discrete Mathematics and Its Applications

5.2 Strong Induction and Well-Ordering 335

EXAMPLE 1 Suppose we can reach the first and second rungs of an infinite ladder, and we know that if we
can reach a rung, then we can reach two rungs higher. Can we prove that we can reach every
rung using the principle of mathematical induction? Can we prove that we can reach every rung
using strong induction?

Solution: We first try to prove this result using the principle of mathematical induction.
BASIS STEP: The basis step of such a proof holds; here it simply verifies that we can reach
the first rung.
ATTEMPTED INDUCTIVE STEP: The inductive hypothesis is the statement that we can
reach the kth rung of the ladder. To complete the inductive step, we need to show that if we
assume the inductive hypothesis for the positive integer k, namely, if we assume that we can
reach the kth rung of the ladder, then we can show that we can reach the (k + 1)st rung of the
ladder. However, there is no obvious way to complete this inductive step because we do not
know from the given information that we can reach the (k + 1)st rung from the kth rung. After
all, we only know that if we can reach a rung we can reach the rung two higher.

Now consider a proof using strong induction.
BASIS STEP: The basis step is the same as before; it simply verifies that we can reach the first
rung.
INDUCTIVE STEP: The inductive hypothesis states that we can reach each of the first k rungs.
To complete the inductive step, we need to show that if we assume that the inductive hypothesis
is true, that is, if we can reach each of the first k rungs, then we can reach the (k + 1)st rung.
We already know that we can reach the second rung. We can complete the inductive step by
noting that as long as k ≥ 2, we can reach the (k + 1)st rung from the (k − 1)st rung because
we know we can climb two rungs from a rung we can already reach, and because k − 1 ≤ k,
by the inductive hypothesis we can reach the (k − 1)st rung. This completes the inductive step
and finishes the proof by strong induction.

We have proved that if we can reach the first two rungs of an infinite ladder and for every
positive integer k if we can reach all the first k rungs then we can reach the (k + 1)st rung, then
we can reach all rungs of the ladder. ▲

Examples of Proofs Using Strong Induction

Now that we have both mathematical induction and strong induction, how do we decide which
method to apply in a particular situation? Although there is no cut-and-dried answer, we can
supply some useful pointers. In practice, you should use mathematical induction when it is
straightforward to prove that P(k) → P(k + 1) is true for all positive integers k. This is the
case for all the proofs in the examples in Section 5.1. In general, you should restrict your use of
the principle of mathematical induction to such scenarios. Unless you can clearly see that the
inductive step of a proof by mathematical induction goes through, you should attempt a proof
by strong induction. That is, use strong induction and not mathematical induction when you
see how to prove that P(k + 1) is true from the assumption that P(j) is true for all positive
integers j not exceeding k, but you cannot see how to prove that P(k + 1) follows from just
P(k). Keep this in mind as you examine the proofs in this section. For each of these proofs,
consider why strong induction works better than mathematical induction.
We will illustrate how strong induction is employed in Examples 2–4. In these examples,
we will prove a diverse collection of results. Pay particular attention to the inductive step in
each of these examples, where we show that a result P(k + 1) follows under the assumption that
P(j) holds for all positive integers j not exceeding k, where P(n) is a propositional function.