Chapter Review 87
duction but not the Principle of Mathematical Induction, that T' = N. Then, use
that to show that every natural number n > no is in T.)
(b) Assuming the (first form of the) Principle of Mathematical Induction, prove the
Strong Form of Mathematical Induction. You need to do the following: Assume
'T C N and that for all n E N, if all k < n are in T, then n (" T. Prove, using
the Principle of Mathematical Induction but not the Strong Form of Mathemati-
cal Induction, that T = N. (Hint: Let T' = {n E N : for all k < n, k E T}. Prove
T' = N, and then use that to prove T = N.)
- How many students are in Math347? From the survey of all the students, it was found
that 43 had taken Econl03, 55 had taken Soci213, 30 had taken Musil 11, 8 had taken
both Econl03 and Soci2l3, 13 had taken both Econl03 and MusilIl, 15 had taken
Soci213 and Musil 11, and 8 had taken none of the courses. No one had taken all three
courses.
- How many integers between 1 and 250, including 1 and 250, are divisible neither by 3
nor by 7 but are divisible by 5?
1.12.4 Using Discrete Mathematics in Computer Science
- Prove that the Largest Odd Divisor algorithm outputs the largest odd divisor of N for
all integers N > 0.
- Prove that the PrintFactors algorithm factors natural numbers N > 1 into primes.
Prove that, in fact, its output is a list of one or more primes whose product is N.
So, for N = 24, the outputs are the numbers 2, 2, 2, and 3, in some order.
- Consider the Binary Search of Phone Directory algorithm. This algorithm looks for
the 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 summation shown arises in determining how long it takes part of one particular
method, called heapsort, to sort a list of numbers into increasing order. More pre-
cisely, heapsort often is written with a preprocessing step called heapify. (Preprocess-
ing means that this step is performed once before the main step of the program.) This
summation arises in determining how long it takes to "heapify" a list of 2n numbers:
0.2n + 1 "2n-1 + 2"2n -2 + 3"-2n-3 +" q-..+(n -- 1) .2' +n-n 20 = 2n+1 --n -- 2
Prove by induction that the summation is correct for n > 0.
- Show by induction on n that for b E N, b > 2,
n
(b - 1). E bi = bn+l - 1
i=O
Interpret this identity in the context of number representation in the base b using the
standard positional notation. Start by seeing what this means for b = 10 and n = 4.
- (a) In the calculation of baseexpont using FastPower, how many copies of the algorithm
will be invoked?
(b) Show that if the FastPower algorithm is invoked n times (that is, n total invoca-
tions, including both the original invocation from the outside and the recursive
invocations), somewhere between 0 and 2n multiplications will be performed.
