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 Mathematical 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.)
13. 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.
14. 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
1. Prove that the Largest Odd Divisor algorithm outputs the largest odd divisor of N for
all integers N > 0.
2. 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.
3. 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.
4. 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 precisely, heapsort often is written with a preprocessing step called heapify. (Preprocessing 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.
5. 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.
6. (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 invocations, including both the original invocation from the outside and the recursive
invocations), somewhere between 0 and 2n multiplications will be performed.
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 Mathematical 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.)
13. 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.
14. 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
1. Prove that the Largest Odd Divisor algorithm outputs the largest odd divisor of N for
all integers N > 0.
2. 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.
3. 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.
4. 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 precisely, heapsort often is written with a preprocessing step called heapify. (Preprocessing 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.
5. 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.
6. (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 invocations, including both the original invocation from the outside and the recursive
invocations), somewhere between 0 and 2n multiplications will be performed.