Mathematics for Computer Science

2.4. Well Ordered Sets 39

(e)Conclude that equation (2.9) holds for all positive integers,n.

Problem 2.12.
Use the Well Ordering Principle (WOP) to prove that

2 C 4 C


C2nDn.nC1/ (2.11)

for alln > 0.

Problem 2.13.
Prove by the Well Ordering Principle that for all nonnegative integers,n:

Xn

iD 0

i^3 D



n.nC1/

2

 2

:

Problems for Section 2.4

Homework Problems

Problem 2.14.
Complete the proof of Lemma 2.4.5 by showing that the numbernSCfSis the
minimum element inS.

Practice Problems

Problem 2.15.
Indicate which of the following sets of numbers have a minimum element and
which are well ordered. For those that are not well ordered, give an example of
a subset with no minimum element.

(a)The integers

p

2.

(b)The rational numbers

p

2.

(c)The set of rationals of the form1=nwherenis a positive integer.

(d)The setGof rationals of the formm=nwherem;n > 0andngwheregis
agoogol, 10100.

(e)The set,F, of fractions of the formn=.nC1/:

0

1

;

1

2

;

2

3

;

3

4

;::::