REVIEW OF MATHEMATICAL INDUCTION - A Book of Abstract Algebra

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), bA, which is impossible. ■

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

image

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

image

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

image

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

image

that is,

image

From this last equation, k + 1 ∈ A.

We have shown that 1 ∈ A, and moreover, that if kA, 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 + ⋯ + (2n − 1) = n2

(That is, the sum of the first n odd integers is equal to n2.)

2 13 + 23 + ⋯ + n3 = (1 + 2 + ⋯ + n)2

3 12 + 22 + ⋯ + n2 = image n(n + 1)(2n + 1)

4 13 + 23 + ⋯ + n3 = image n(n + 1)2

5 image

6 12 + 22 + ⋯ + (n − 1)2 < image < 12 + 22 + ⋯ + n2