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 ﬁrst door.

The prize is that equ ation (B.1) is true when n = 1. Step 2 veriﬁes 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

3

+ ···+ 2

n−1

= 2

n

− 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 inﬁnitely 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

3

+ ···+ 2

n−1

= 2

n

− 1}.

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.