Appendix B

Mathematical Indu ction and the

Well-Ordering Principle

Focus Questions

By the end of this investigation, you should be able to give precise and thorough

answers to the questions listed below. You may want to keep these questions in mind

to focus your tho ughts as you complete the investigation.

• What does the Principle of Mathematical Induc tion say? Wh at do we need to verify

in order to prove a statement using the Principle of Mathem a tical In duction?

• How do the extended and strong forms o f induction differ from the Principle of

Mathematical Induction? How are all of these different versions of induction sim-

ilar?

• What does the Well-Ordering Principle say? Wh at do we need to verify in order

to prove a statement using the Well-Ordering Principle?

• How are the Principle of Mathematical Induction, the Extended Principle of Math-

ematical Induction, the Strong Form of Mathematical Induction, and the Well-

Ordering Princ iple all re late d?

Preview Activity B.1. Suppose you a re o n a game show called Let’s Make a Great Deal. You have

reached the ﬁnal round and will be asked one question. If you answer the question correctly, you

will win a key to open door number 1. Behind door number 1 is a prize and a key to open door

number 2. Behind door number 2 is a prize and a key to open door number 3. Behind door number

3 is a pr iz e and a key to open door n umber 4, and so on.

(a) How many prizes will you win if you fail to answer the q uestion correctly?

(b) Wh ich prizes will yo u win if you answer the question correctly?

Introduction

Mathematical induction is an important tool in mathematics. Induction helps us prove that certain

types of statements are true for all positive integers. This is quite a feat, since there are inﬁnitely

549

550 Appendix B. Mathematical Induction and the Well-Ordering Princip le

many positive integers! Mathematical induction comes in more than on e ﬂavor. There is the basic

principle, the extended principle, and the strong (or second, or complete) principle. An equ ivalent

version of the Principle of Mathematica l Induction is the Well-Ordering Principle. We will study

each of these principles in this investigation.

The Principle of Mathematical Induc tion

Activity B.1 demonstrated the basic idea behind induction. Just as no prize comes for free (in our

game, we needed to answer the question in orde r to win anything), to verify a statement usin g

induction, we will need to prove something. In other words, we will need to unlock the door that

has our ﬁrst statement be hind it. But unloc king the ﬁrst door is not en ough to unlock every other

door, unless we are able to establish—as was speciﬁed in the rules of our game show—that each

door, when opened, contains the key to the next door. If this condition also holds, then once we open

the ﬁrst door—that is, once we prove the ﬁr st statement—we will be able to open every other door,

thus proving o ur statement for eve ry positive integer.

To illustrate this proce ss in a mo re concrete way, consider the example in the following activity.

Activity B.2. Let n be a positive integer. Complete Tab le B.2. What do you notice?

n 1 + 2 + 3 + ··· + n

n(n+1)

2

1

2

3

4

5

The calculations in Activity B.2 show that

1 + 2 + 3 + ··· + n =

n(n + 1)

2

(B.1)

for all integers n between 1 and 5. A few more calc ulations might convince you that equ ation (B.1)

is actually true for many more integers, and perhaps for all positive integers. Although we cannot

physically evaluate both sides of equation (B.1) to determine if it is true for every positive integer,

we can use mathematical induction to accomplish the same goal.

To return to our game show analogy, think of verifying equation (B.1) as the g oal of the game.

Each door corresponds to one instance of equation (B.1). The ﬁrst door corresponds to equation

(B.1) with n = 1, the second door to equation (B.1) with n = 2, and so on. In general, for each

positive integer m, the m

th

door corresponds to equation (B.1) with n = m.

In this con text, the question we need to answer to open door number one is whether equation

(B.1) is true when n = 1 .

Activity B.3. Is equation (B.1) is true when n = 1? Why?

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.