Induction
Prove the following using induction:
(a) For all natural numbers n 2, 2n 2n+1.
(b) For all positive integers n, 13 +33 +53 +···+(2n−1)3 =n2(2n2 −1).
(c) For all positive natural numbers n, is divisible by 19.
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 Bit String
Prove that every positive integer n can be written with a string of 0s and 1s. 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}.
