Reading Quiz Section 5.1
1. In an induction proof of the fact that P(n) is true for all n ∈ N, the base case consists of proving
that
(a) P(1) is false.
(b) P(1) is true.
(c) For all n, P(n) =⇒ P(n + 1).
(d) P(1) =⇒ P(2).
2. In an induction proof of the fact that P(n) is true for all n ∈ N, the induction hypothesis is the
assumption that
(a) P(1) is true.
(b) For all n, P(n) =⇒ P(n + 1).
(c) P(n) is true for some fixed n ∈ N.
(d) P(n) is true for all n ∈ N.
3. True or False: in formal proofs, it is acceptable to write
P(n) =
n
∑
i =1
k =
1
2
n(n + 1)
as shorthand for “P(n) is the proposition
∑
n
i =1
k =
1
2
n(n + 1).”
Practice Problems Section 5.1
1. (a) Prove by induction that ∀n ∈ N we have 3 | (2
n
+ 2
n+1
).
(b) Give a direct proof that 3 | (2
n
+ 2
n+1
) for all integers n ≥ 1 and for n = 0.
(c) Look carefully at your proof for part (a). If you had started with the base case n = 0
instead of n = 1, would your proof still be valid?
Video Solution
