5.4 PROOF .BY MATHEMATICAL INDUCTION 187- (a) Prove, by induction, that 3 divides 4" - 1 for all n E N.
(b) Prove that, for any x E Z, x - 1 divides x" - 1 for all n E N.
(c) Prove that 5 divides 8" - 3" for all n E N.
*(d) Prove that, for any integers x and y, x - y divides xu - y", n = 1, 2, 3,...
(e) Prove that 6 divides n3 - n for all n E: N. - Prove, using the modified induction approach suggested by Theorem 2;
(a) If n 2 5, then n2 < 2" (b) If n 2 10, then n3 < 2"
(c) If n^2 17, then n4 < 2" (d) If n 2 9, then 4" < n!
(e) If n 2 2, then z= (I/&) > ,h.
9. (a) Prove that if x is a real number greater than - 1 and if n is a positive
integer, then (1 + x)" r 1 + nx.
(b) Prove that if n is a positive integer and
(i) Ifx>l,thenxn> 1 (ii) Ifx<O,then~~"-~<O
(iii) If x # 0, then x2" > 0 (iv) If x 2 1, then x" 2 x
(v) If 0 < a < b, then^0 < a" < b"
(c) ..., n,thenIanI<n.
10. Each of the following predicates over N is false for all positive integers. Verify
in each case that the condition (Vn)(p,(n) -+ p,(n + 1)) is true:
11. The formula n2 - n + 41 yields primes for n = 1,2,3,... ,40.
(a) Verify this for five specific cases.
(b) Prove or disprove that this formula yields a prime for all positive integers n.
12. (a) Prove that the empty set 12j is inductive.
(b) Use Theorem 2, together with the well-ordering principle for N (i.e., the axiom'
every nonempty subset of N has a smallest element), to prove that every nonempty"
inductive subset of N has the form (m, m + 1, m + 2,.. .) for some positive
integer m.
(c) ~Onclude from (b) that every inductive subset of N is either empty or infinite.
.-- .,------- - (a) Prove, by induction on n, that if A is a set with n elements (n E N), then
9(A) has 2" elements.
(b) Assume that he sum of the interior angles of a a triangle is 180". Use this
result to prove, by induction, that the sum of the interior angles of an n-sided
convex polygon (n 2 3) is 180" times (n - 2). - Determine what is wrong with the following "proof' by induction of the "theo-
rem": All sets in any collection of n sets are equal.
"Proof" Let S be the set of those positive integers for which the result is true.
Thus m E S if and only if all sets in any collection of rn sets are equal. (1 ) Clearly
1 E S, since every set equals itself. (2) Assume m E S. To prove m + 1 E S,