552 Appendix B. Mathematical Induction and the Well-Ordering Princip le
Use this assumption to show that equatio n (B.1) is true for n + 1.
To summarize, we needed to prove two things to show that equation (B.1) is true for all positive
integers n:
(1) Equ ation (B.1) is true when n = 1; and
(2) whenever equation (B.1) is true for a positive integer n, then it is also true for the integer
n + 1.
Step 1 is equivalent to answering the question in our game show and opening the first door.
The prize is that equ ation (B.1) is true when n = 1. Step 2 verifies that ea c h door holds the key to
opening the next—that is, if equation (B.1) is true for the integer n, then it is also true for n + 1.
Completing both steps shows that equation (B.1) is true for every positive integer n.
Let’s now formalize the ideas from the previous example. In doing so, we will develop the
Principle of M athematical Induction, which can be used when we have a family of statements, one
for each positive integer, that we want to prove. For example, for ea c h positive integer n, let P (n)
be th e statement that
1 + 2 + 2
+ 2
+ ···+ 2
= 2
1 (B.3)
To prove that P (n) is true for all n N, we have seen that we need to prove that:
(1) P (1) is true (we call this the base case); and
(2) for every positive integer n, if P (n) is true, then P (n + 1) is also true. (This second step is
called the inductive step.)
When we prove the inductive step, we assume P (n) is true for some ar bitrary positive integer
n. Th is assum ption is called the ind uction hypo thesis or inductive hypo thesis. We th e n show, using
this assumption, that P (n + 1) is also true.
Rephrasing this process in a slightly different form leads us to the formal statement of the Princi-
ple o f Mathematical Induction. Let S b e the set of positive integers for which P (n) is true. Proving
P (1) is true is the same as showing that 1 is in S. Likewise, showin g that P (n) implies P (n + 1)
is equivalent to showing that n + 1 S whenever n S. Combining these two observations, we
arrive at th e following axiom:
Axiom B.5 (Principle o f Mathematical Induction). Let S be a subset of the set of na tural numbers
N. If
(i) S contains 1 and
(ii) S contains the positive integer n + 1 whenever S contains n,
then S = N.
In essence, the Principle of Mathematical Induction tells us that if we have a set S N contain-
ing 1, and if S contains th e integer n + 1 whenever S contains n, then S must contain 1 + 1 = 2.
But then S must also contain 2 + 1 = 3, and 3 + 1 = 4 , and so on. Therefore, S will contain all
natural numbers. By using the Principle of Mathematical Induction, we can prove infinitely many
statements in only two steps.
To illustrate, let’s formally ap ply the Principle of Mathematical Induction to establish equatio n
(B.3). Let
S = {n N : 1 + 2 + 2
+ 2
+ ···+ 2
= 2

Get Abstract Algebra now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.