Page 355 - Discrete Mathematics and Its Applications

334 5 / Induction and Recursion

two forms of mathematical induction. In this section we will give some examples of how the
well-ordering property can be used to prove theorems.

Strong Induction

Before we illustrate how to use strong induction, we state this principle again.

STRONG INDUCTION To prove that P (n) is true for all positive integers n, where P (n)
is a propositional function, we complete two steps:
BASIS STEP: We verify that the proposition P(1) is true.
INDUCTIVE STEP: We show that the conditional statement [P(1) ∧ P(2) ∧ ··· ∧
P(k)]→ P(k + 1) is true for all positive integers k.

Note that when we use strong induction to prove that P (n) is true for all positive integers n,
our inductive hypothesis is the assumption that P(j) is true for j = 1, 2,...,k. That is, the
inductive hypothesis includes all k statements P(1), P(2),...,P(k). Because we can use all k
statements P(1), P(2),...,P(k) to prove P(k + 1), rather than just the statement P(k) as in a
proof by mathematical induction, strong induction is a more flexible proof technique. Because
of this, some mathematicians prefer to always use strong induction instead of mathematical
induction, even when a proof by mathematical induction is easy to find.
You may be surprised that mathematical induction and strong induction are equivalent.
That is, each can be shown to be a valid proof technique assuming that the other is valid. In
particular, any proof using mathematical induction can also be considered to be a proof by strong
induction because the inductive hypothesis of a proof by mathematical induction is part of the
inductive hypothesis in a proof by strong induction. That is, if we can complete the inductive
step of a proof using mathematical induction by showing that P(k + 1) follows from P(k) for
every positive integer k, then it also follows that P(k + 1) follows from all the statements P(1),
P(2),...,P(k), because we are assuming that not only P(k) is true, but also more, namely, that
the k − 1 statements P(1), P (2),...,P(k − 1) are true. However, it is much more awkward to
convert a proof by strong induction into a proof using the principle of mathematical induction.
(See Exercise 42.)
Strong induction is sometimes called the second principle of mathematical induction
or complete induction. When the terminology “complete induction” is used, the principle of
mathematical induction is called incomplete induction, a technical term that is a somewhat
unfortunate choice because there is nothing incomplete about the principle of mathematical
induction; after all, it is a valid proof technique.

STRONG INDUCTION AND THE INFINITE LADDER To better understand strong in-
duction, consider the infinite ladder in Section 5.1. Strong induction tells us that we can reach
all rungs if

1. we can reach the first rung, and
2. for every integer k, if we can reach all the first k rungs, then we can reach the (k + 1)st rung.

That is, if P(n) is the statement that we can reach the nth rung of the ladder, by strong induction
we know that P(n) is true for all positive integers n, because (1) tells us P(1) is true, completing
the basis step and (2) tells us that P(1) ∧ P(2) ∧ ··· ∧ P(k) implies P(k + 1), completing the
inductive step.
Example 1 illustrates how strong induction can help us prove a result that cannot easily be
proved using the principle of mathematical induction.