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 + ⋯ + (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 = n(n + 1)(2n + 1)
4 13 + 23 + ⋯ + n3 = n(n + 1)2
5
6 12 + 22 + ⋯ + (n − 1)2 < < 12 + 22 + ⋯ + n2