Description

CS 70 Discrete Mathematics and Probability Theory

1 Induction
Prove the following using induction:
(a) Let a and b be integers with a 6=b. For all natural numbers n ≥ 1, (an −bn) is divisible by (a−b).
(b) For all natural numbers n, (2n)! ≤ 22n(n!)2. [Note that 0! is defined to be 1.]
2 Make It Stronger
Suppose that the sequence a1,a2,… is defined by a1 = 1 and an+1 = 3an2 for n ≥ 1. We want to prove that
an ≤ 32n
for every positive integer n.
(a) Suppose that we want to prove this statement using induction, can we let our induction hypothesis be simply an ≤ 32n? Show why this does not work.
(b) Try to instead prove the statement an ≤ 32n−1 using induction. Does this statement imply what you tried to prove in the previous part?
3 Binary Numbers
Prove that every positive integer n can be written in binary. In other words, prove that we can write
n=ck·2k+ck−1 ·2k−1 +···+c1 ·21 +c0 ·20,
where k ∈ N and ck ∈ {0,1}.