## A Book of Abstract Algebra, Second Edition (1982)

### APPENDIX C. REVIEW OF MATHEMATICAL INDUCTION

The basic assumption one makes about the ordering of the integers is the following:

**Well-ordering principle**. *Every nonempty set of positive integers has a least element*.

From this assumption, it is easy to prove the following theorem, which underlies the method of proof by induction:

**Theorem 1: Principle of mathematical induction** *Let A represent a set of positive integers. Consider the following two conditions:*

(i)1 *is in A*.

(ii)*For any positive integer k*, *if k is in A*, *then k* + 1 *is in A*.

*If A is any set of positive integers satisfying these two conditions, then A consists of all the positive integers*.

PROOF: If *A* does not contain all the positive integers, then by the well-ordering principle (above), the set of all the positive integers which are *not* in *A* has a least element; call it *b*. From Condition (i), *b* ≠ 1; hence *b* > 1.

Thus, *b* − 1 > 0, and *b* — 1 ∈ *A* because *b* is the *least* positive integer *not* in *A*. But then, from Condition (ii), *b* ∈ *A*, which is impossible. ■

Here is an example of how the principle of mathematical induction is used: We shall prove the identity

that is, the sum of the first *n* positive integers is equal to *n*(*n* + 1)/2.

Let *A* consist of all the positive integers *n* for which __Equation (1)__ is true. Then 1 is in *A* because

Next, suppose that *k* is any positive integer in *A*; we must show that, in that case, *k* + 1 also is in *A*. To say that *k* is in *A* means that

By adding *k* + 1 to both sides of this equation, we get

that is,

From this last equation, *k* + 1 ∈ *A*.

We have shown that 1 ∈ *A*, and moreover, that if *k* ∈ *A*, then *k* + 1 ∈ *A*. So by the principle of mathematical induction, all the positive integers are in *A*. This means that __Equation (1)__ is true for every positive integer, as claimed.

**EXERCISES**

*Use mathematical induction to prove the following:*

**1** 1 + 3 + 5 + ⋯ + (2*n* − 1) = *n*^{2}

(That is, the sum of the first *n* odd integers is equal to *n*^{2}.)

**2** 1^{3} + 2^{3} + ⋯ + *n*^{3} = (1 + 2 + ⋯ + *n*)^{2}

**3** 1^{2} + 2^{2} + ⋯ + *n*^{2} = *n*(*n* + 1)(2*n* + 1)

**4** 1^{3} + 2^{3} + ⋯ + *n*^{3} = *n*(*n* + 1)^{2}

**5**

**6** 1^{2} + 2^{2} + ⋯ + (*n* − 1)^{2} < < 1^{2} + 2^{2} + ⋯ + *n*^{2}