5.4 PROOF BY MATHEMATICAL INDUCTION 179To a very large extent, theorems whose statement involves the phrase
"for all positive integers n," are the theorems for which an induction proof
is appropriate. As we will see later, induction proofs may be appropriate
in a slightly more general context that includes (c) of Example 1.
Suppose now we wish to prove a statement (Vn)(p(n)), where N is the
domain of discourse for the predicate p(n). Denote by S the subset of N
consisting of all positive integers for which p(n) is true. In the terminology
of Chapter 3, S is the truth set of p(n). By definition, S is a subset of N.
To prove our theorem, we must prove that S equals N. Clearly a criterion
giving a general approach to proving that a subset S of N actually equals
N should have potential for being applied to this situation. The principle
of mathematical induction is just such a criterion.
T H E 0 R E M 1 (Principle of Mathematical Induction)
Let S be a subset of the set N of all positive integers satisfying the properties:
(i) 1 E S
(ii) For all n E N, if n E S, then n + 1 E S.
Then S = NIt is intuitively evident that N satisfies conditions (i) and (ii) of Theo-
rem 1. Another way of stating Theorem 1 is that no proper subset of N
satisfies both conditions (i.e., the only subset of N satisfying both condi-
tions is N itself). We defer a formal proof in the text of Theorem 1 until
Chapter 10, where we study N as a number system and consider a number
of its properties (see also Exercise 9(d), Article 6.3). We note here, however,
that the result is not difficult to believe. For example, assume that a subset
S of N satisfies (i) and (ii) and suppose we wish to conclude 3 E S. To do
this, we observe simply that 1 E S, by (i). Combining this fact with (ii), using
specialization, we conclude that 2 = 1 + 1 E S. Since 2 E S, then, again
using (ii), we conclude 3 = 2 + 1 E S, as desired. The same argument, in-
volving n repetitions, can in theory be used to prove that any given positive
integer n is in S.
We shift our attention now away from the validity of Theorem 1 and
toward its application.
EXAMPLE 2 Prove that the sum of the first n odd positive integers is given
by the formula n2, in symbols, for all n E N, 1 + 3 + 5 +... + (2n - 1) = n2.
Solution Before attempting to write a proof of a statement, we find it a
good idea to try a few cases, to see whether the result stated is reasonable.
For example, if n = 10, the result states that 1 + 3 + 5 +. + 17 + 19 =
100, as computation quickly verifies. You should try several other cases.
Now for the proof, let S be the subset of N consisting of those posi-
tive integers m for which the result is true. Our claim is that S = N. To