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 final 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 infinitely
549
550 Appendix B. Mathematical Induction and the Well-Ordering Princip le
many positive integers! Mathematical induction comes in more than on e flavor. 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 first statement be hind it. But unloc king the first door is not en ough to unlock every other
door, unless we are able to establish—as was specified 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 first door—that is, once we prove the fir 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 first 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.