Mathematics for Computer Science

Chapter 2 The Well Ordering Principle38

Assume for the purpose of obtaining a contradiction thatCis nonempty.

Then by the WOP, there is a smallest number,m 2 C. ThenS.m10/

orS.m15/must hold, because themcents postage is made from 10

and 15 cent stamps, so we remove one.

So supposeS.m10/holds. Then 5 j.m10/, because...

But if 5 j.m10/, then 5 jm, because...

contradicting the fact thatmis a counterexample.

Next supposeS.m15/holds. Then the proof form 10 carries

over directly form 15 to yield a contradiction in this case as well.

Since we get a contradiction in both cases, we conclude thatC must

be empty. That is, there are no counterexamples to (2.8), which proves

that (2.8) holds.

The proof makes an implicit assumption about the value ofm. State the assump-
tion and justify it in one sentence.

Problem 2.11.
We’ll use the Well Ordering Principle to prove that for every positive integer,n, the
sum of the firstnodd numbers isn^2 , that is,

nX 1

iD 0

.2iC1/Dn^2 ; (2.9)

for alln > 0.
Assume to the contrary that equation (2.9) failed for some positive integer,n.
Letmbe the least such number.

(a)Why must there be such anm?

(b)Explain whym 2.

(c)Explain why part (b) implies that

mX 1

iD 1

.2.i1/C1/D.m1/^2 : (2.10)

(d)What term should be added to the left hand side of (2.10) so the result equals

Xm

iD 1

.2.i1/C1/‹