Bridge to Abstract Mathematics: Mathematical Proof and Structures

5.4 PROOF BY MATHEMATICAL INDUCTION 185

DEFINITION 1

A subset S of the set N of all positive integers is said to be inductive if and only

if m E S implies m + 1 E S for all positive integers m.

Since the condition of Definition 1 is simply condition (ii) of Theorem
1, it is clear that N itself is inductive. In fact, for any positive integer n,
the subset (n, n + 1, n + 2,.. .) of N is also inductive. Furthermore, we
have the following theorem.

THEOREM 2

Suppose S is an inductive subset of N containing a positive integer m,.

Then S contains m for every positive integer m greater than m,: that is,

{mo,m,+1,m,+2 ,... )sS.

Proof Consider the set T = S u (l,2,... , m, - 1). Clearly 1 E T and T is
inductive (Verify the latter claim, using the technique of division into
cases together with the fact that S is inductive). Hence, by Theorem 1,
T = N. Choose m E N such that m > m,. We will have completed the
proof if we can show m E S. Since T = N, then we have m E N = T =
S u 1 2,... , m - 1 Since m > m,, then m q! (1,2,... , m, - 1) so
that we may conclude m E S, as desired.

The upshot of Theorem 2 is that we may prove a theorem asserting
(Vn 2 no)(p(n)) by proving that the truth set S of p(n) satisfies (i) no E S and
(ii) S is inductive. In fact, we may substitute for (ii) the slightly weaker
condition (ii)': for all m E N, m E S and m 2 no together imply m + 1 E S.

EXAMPLE 8 Prove that if n is an integer and n 2 4, then 2" <'n!.

Solution Let S be the truth set of p(n): 2n < n!. We claim that (4, 5,6,... ,) E
S. Note first that 4 E S since Z4 = 16 < 24 = 4!. Second, suppose that
m 2 4 and m E S, so that 2'" < m!. We must prove, on the basis of these
assumptions, that 2'"' < (m + I)!. But 2'"' = 2(2") < 2(m!) < (m + l)m! =
(m + I)!, as desired.
Note that the induction hypothesis was used in the step 2(2'") < 2(m!).
0

You may have already conjectured that every inductive subset of N has

the form (m, m + 1, m + 2,.. .)for some positive integer m. This conjecture

is nearly true; in order to make it true, we must insert the word nonempty

before "inductive." The reason for this is that the empty set @ is inductive.

The latter fact is another reason we must never neglect to verify condition

(i) in any induction proof. If a statement p(n) with domain of discourse N

has a truth set that is inductive [i.e., condition (ii) can be proved], it may

still be the case that p(n) is false for all n E N, that is, S = 0 (see Exercise

10). But if p(n) has an inductive truth set and furthermore is true for at