Section 2.2 Induction
119
PRinciPLe PrINCIPlE oF WEll-orDErINg
Every collection of positive integers that contains any members at all has a
smallest member.
We will see that the following implications are true:
second principle of induction S first principle of induction
first principle of induction S well-ordering
well-ordering S second principle of induction
As a consequence, all three principles are equivalent, and accepting any one of
them as true means accepting the other two as well.
To prove that the second principle of induction implies the first principle of
induction, suppose we accept the second principle as valid reasoning. We then
want to show that the first principle is valid; that is, that we can conclude P(n) for
all n from statements 1 and 2. If statement 1 is true, so is statement 1′. If statement
2 is true, then so is statement 2′, because we can say that we concluded P(k + 1)
from P(r) for all r between 1 and k, even though we used only the single condition P(k). (More precisely, statement 2′ requires that we prove P(l) ` P(2) ` g
` P(k) S P(k + 1), but P(l) ` P(2) ` g` P(k) S P(k), and from statement 2,
P(k) S P(k + 1), so P(1) ` P(2) ` g` P(k) S P(k + 1).) By the second principle of induction, we conclude P(n) for all n. The proofs that the first principle
of induction implies well-ordering and that well-ordering implies the second
principle of induction are left as exercises in Section 4.1.
To distinguish between a proof by the first principle of induction and a proof
by the second principle of induction, let’s look at a rather picturesque example that
can be proved both ways.
eXAMPLe 21
Prove that a straight fence with n fence posts has n – 1 sections for any n ≥ 1 (as
in Figure 2.4a).
Fence with 4 fenceposts, 3 sections
Fence with 1 fencepost, 0 sections
(a)
(b)
Fence with last post and
last section removed
Fence with 1 section removed
(c)
(d)
Figure 2.4