Chapter Review 81
- Challenge: There is a third principle related to induction, the Principle of Well-
Ordering for the Natural Numbers. It is the following: If T C N and T A 0, then
T contains a minimum element; that is, there is a natural number no E T such that for
all natural numbers k < no, we have k g T.
(a) Use the Principle of Well-Ordering for the Natural Numbers instead of the Strong
Form of Mathematical Induction to prove that
n .(n + 1)
2
(Hint: Let T={n EN:0+l+2+...+n n.(n+1)/2}.)
(b) Use the Principle of Well-Ordering for the Natural Numbers instead of the Strong
Form of Mathematical Induction to prove that every integer n such that n > 1 can
be factored into a product of one or more primes.
(c) Using the Principle of Well-Ordering for the Natural Numbers, prove one of the
forms of the Principle of Mathematical Induction.
(d) Using one of the forms of the Principle of Mathematical Induction, prove the Prin-
ciple of Well-Ordering for the Natural Numbers.
- The Binary Search of Phone Directory algorithm in Section 1.10.4 looks for any page
(if any) containing a name Name in a telephone book City. The portion of the algorithm
used in searching for the page is called BinarySearch. Prove that the algorithm works
correctly.
The language of sets was introduced. The basic operations of union, intersection, set dif-
ference, and complementation were studied. The properties of these operations were given
as well as the properties of these operations when they are used with each other. One im-
portant way that union, intersection, and complementation interact is through DeMorgan's
Laws. Finally, the power set of a set and the product of two sets are introduced. The proof
techniques used with sets are highlighted as templates for an idea of how to approach sim-
ilar proofs. The chapter then moves to the topic of determining the number of elements in
a set of overlapping sets using the Principle of Inclusion-Exclusion. The last two sections
introduce extremely important proof techniques for proving results about the natural num-
bers. Both the Principle of Mathematical Induction and the Strong Form of Mathematical
Induction are explained and used in constructing proofs of statements about natural num-
bers. The basic idea of a pseudocode that is used to present algorithms is described for use
throughout.
Set operations are used as examples of operations that define boolean algebras and
lattices. Induction is used to study Fibonacci numbers and geometric series. Important
examples regarding the use of induction in both forms in proving an algorithm is correct are
given. For example, algorithms for computing powers, finding factorizations of an integer,
and carrying out an efficient search are proven to be correct algorithms.
