CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Prove or Disprove
Prove or disprove each of the following statements. For each proof, state which of the proof types (as discussed in Note 2) you used.
(a) For all natural numbers n, if n is odd then n2 + 3n is even.
(b) Forallrealnumbersa,b,ifa+b≥20thena≥17orb≥3.
(c) For all real numbers r, if r is irrational then r + 1 is irrational.
(d) For all natural numbers n, 10n3 > n!.
(e) For all natural numbers a where a5 is odd, then a is odd.
2 Twin Primes
(a) Let p > 3 be a prime. Prove that p is of the form 3k+1 or 3k−1 for some integer k.
(b) Twin primes are pairs of prime numbers p and q that have a difference of 2. Use part (a) to prove that 5
is the only prime number that takes part in two different twin prime pairs.
CS 70, Fall 2021, DIS 1B 1
3 Induction
Prove the following using induction:
(a) For all natural numbers n > 2, 2n > 2n+1.
(b) For all positive integers n, 12 +22 +32 +···+n2 = n(n+1)(2n+1). 6
(c) For all positive natural numbers n, 54 · 8n + 33n−1 is divisible by 19.
4 Make It Stronger
Suppose that the sequence a1,a2,… is defined by a1 = 1 and an+1 = 3a2n for n ≥ 1. We want to prove that an ≤ 3(2n)
for every positive integer n.
(a) Suppose that we want to prove this statement using induction. Can we let our inductive hypothesis be
simply an ≤ 3(2n)? Attempt an induction proof with this hypothesis to show why this does not work.
(b) Try to instead prove the statement an ≤ 3(2n−1) using induction.
(c) Why does the hypothesis in part (b) imply the conclusion from part (a)?
CS 70, Fall 2021, DIS 1B 2