Discrete Mathematics for Computer Science

84 CHAPTER 1 Sets, Proof Templates, and Induction

1.10 Summary

TERMS

base cases prime numbers

base step(s) recursion

closed form recursive call

inductive hypothesis recursively defined sequence

inductive step

THEOREMS

Fundamental Theorem of Arithmetic

Strong Form of Mathematical Induction

ALGORITHMS

Compute Powers Binary Search of Phone Directory

Largest Odd Divisor Compute F,

Print a Prime Factorization of an Integer

TEMPLATE

Template 1.13 Using the Strong Form of

Mathematical Induction

1.12.2 Starting to Review

1. Which of the following set descriptions gives the set {2, 8, 14, 20, 26, 32)?

(a) {n E N :n = 2x + 6 for some integer x such that I < x < 6)

(b) {n e N: n = 6x + 2 for some integer x such that I < x < 6)

(c) {n E N n = 6x + 2 for some integer x such that 0 < x < 6}

(d) None of the above

2. Let B = {2, 3, 6, 9, 111 and C = {1, 4, 6, 11, 15). Which of the following sets are not
   any of B U C, B fl C, and B - C?
   (a) {1, 6, 9, 151
   (b) {6, 11)
   (c) {2, 3, 9}
   (d) None of the above


3. What is the contrapositive of the statement "If the sun is shining, then it is time to go
   outside."
   (a) If the sun is shining, then it is not time to go outside.
   (b) If it is time to go outside, then the sun is shining.
   (c) If it is not time to go outside, then the sun is not shining.
   (d) None of the above.