Concluding Activities 565
Concluding Act ivities
Activity B.22. Complete the proof of Theorem B.20 by proving that the Well-Ordering Principle
implies the Principle of Mathematica l Induction. (Hint: If S is a subset of N that contains 1 and also
contains n + 1 whenever S contains n, consider the set T of a ll natural numbers that are not in S.)
(1) In calculus, we often use the fact that
for every positive integer n, but we
usually don’t provide a rig orous proof of this result. Use induction to verify this derivative
formu la. Assume the product rule if you need it.
(2) Prove that
+ ···+ n
n(n + 1)(2n + 1)
for every positive integer n.
(3) In the mid 20
century, the mathema tician George P´olya suggested the apparent paradox that
all girls have eyes of the same color.
His indu ction argument to verify this statement is as
For n = 1 the statement is obviou sly (or “vacuously”) true. It remains to pass
from n to n + 1. For the sake of concreteness, I shall pass fro m 3 to 4 and leave
the g eneral case for you.
Let me introduce you to any four girls, Ann, Berthe, Carol, and Dorothy, or A, B,
C, and D, for short. Allegedly (n = 3) the eyes of A, B, and C ar e of the same
color. Consequently, the eyes of all four girls A, B, C, and D, must be of the same
color; for the sake of full clarity, you may look at the diag ram:
A + B + C + D
This proves the point for n + 1 = 4, and the passage from 4 to 5, f or example, is,
obviously, not more difﬁcult.
A quick glance into the eyes of several girls will show that not all girls have the sam e eye
color, so there must be a ﬂaw in the argument. Find and explain the ﬂaw.
(4) Consider the conjecture
1 + 2 + 3 + 4 + ···+ n =
This appears in P´olya’s 1954 work Induction and Analogy in Mathematics, volume 1 of Mathematics and Plausible
Reasoning, Princeton University Press.