MOE H3 Math Proofs and Reasoning Problem Set 3 Solutions

MOE H3 Math Mathematical Proofs and Reasoning Problem Set 3 1. Use Mathematical Induction to prove the following: (a) For each positive integer n, 1(1!) + 2(2!) + 3(3!) +· · ·+ n(n!) = (n + 1)! − 1. Solution: Let P (n) : 1(1!) + 2(2!) + 3(3!) +· · ·+ n(n!) = (n + 1)! − 1. Basis step: Let n = 1. Left side has just one term, namely 1(1!) = 1. Right side is (1 + 1)! − 1 = 1. So P (1) is true. Inductive step: Assume P (k) is true. So 1(1!) + 2(2!) + 3(3!) +· · ·+ k(k!) = (k + 1)! − 1. We now add (k + 1)[(k + 1)!] to both sides of this equation. This gives 1(1!) + 2(2!) + 3(3!) +· · ·+ k(k!) + (k + 1)[(k + 1)!] = ( k + 1)! − 1 + (k + 1)[(k + 1)!] = [( k + 1)!](k + 2) − 1 = ( k + 2)! − 1 This proves that if P (k) is true, then P (k + 1) is true. Hence by Mathematical induction, we have proven: For each positive integer n, 1(1!) + 2(2!) + 3(3!) +· · ·+ n(n!) = (n + 1)! − 1. (b) For each positive integer n, (−7)n − 9n is divisible by 16. Solution: Let P (n) : (−7)n − 9n is divisible by 16. Basis step: Let n = 1. ( −7)1 − 91 = −16 is divisible by 16. So P (1) is true. Inductive step: Assume P (k) is true. So (−7)k − 9k is divisible by 16, which means ( −7)k − 9k = 16a for some integer a. We now multiply 9 to both sides of this equation. This gives 9[(−7)k − 9k] = 9(16 a) 9(−7)k − 9k+1 = 9(16 a) (16 − 7)(−7)k − 9k+1 = 9(16 a) (−7)(−7)k − 9k+1 = 9(16 a) − (16)(−7)k (−7)k+1 − 9k+1 = 16[9 a − (−7)k] i.e. ( −7)k+1 − 9k+1 is divisible by 16. This proves that if P (k) is true, then P (k + 1) is true. Hence by Mathematical induction, we have proven: For each positive integer n, (−7)n − 9n is divisible by 16.

H3 Math (Mathematical Proofs and Reasoning) Problem Set 3 (c) For each positive integer n with n ≥ 3,

1 + 1 n n < n. Solution: Let P (n) :

1 + 1 n n < n. Basis step: Let n = 3. Since

1 + 1 3 3 = 4 3 3 = 64 27 < 3, so P (3) is true. Inductive step: Assume P (k) is true (with k ≥ 3). This means

1 + 1 k k < k (∗). Multiplying

1 + 1 k

on both sides of ( ∗), we have

1 + 1 k k+1 < k

1 + 1 k

= k + 1 ( ∗∗) On the other hand, since 1 k + 1 < 1 k , then 1 + 1 k + 1 < 1 + 1 k and hence

1 + 1 k + 1 k+1 <

1 + 1 k k+1 (∗ ∗ ∗). Combining (∗∗) and ( ∗ ∗ ∗), we have

1 + 1 k + 1 k+1 < k+ 1. This proves that if P (k) is true, then P (k + 1) is true. Hence by Mathematical induction, we have proven: For each positive integern with n ≥ 3,

1 + 1 n n < n. (d) For each positive integer n with n ≥ 6, n3 < n!. Solution: Let P (n) : n3 < n!. Basis step: Let n = 6. 63 = 216 and 6! = 720 > 63. So P (6) is true. Inductive step: Suppose P (k) is true where k ≥ 6 (i.e. k! > k3). To show P (k + 1) is true. First of all, note that ( k + 1)2 = k2 + 2k + 1 < k2 + k2 + k2 = 3k2 ≤ k3 (∗) when k ≥ 3. Page 2

H3 Math (Mathematical Proofs and Reasoning) Problem Set 3 Now (k + 1)! = ( k + 1)k! > (k + 1)k3 induction hypothesis > (k + 1)(k + 1)2 by (*) = ( k + 1)3 This proves that if P (k) is true, then P (k + 1) is true. Hence by Mathematical induction, we have proven: n! > n3 for all n ≥ 6. 2. Let f1, f2, . . . , fn, . . .be the Fibonacci sequence. i.e. The sequence is defined recursively by f1 = 1 and f2 = 1 fn = fn−1 + fn−2 for all n ≥ 3 Prove each of the following: (a) For each positive integer n, f5n is a multiple of 5. Solution: Let P (n) : f5n is a multiple of 5. Basis step: Let n = 1. We see that f5 = 5 which is divisible by 5. So P (1) is true. Inductive step: Assume P (k) is true. This means f5k is a multiple of 5. Now f5(k+1) = f5k+5 = f5k+4 + f5k+3 = ( f5k+3 + f5k+2) + (f5k+2 + f5k+1) = f5k+3 + 2f5k+2 + f5k+1 = ( f5k+2 + f5k+1) + 2(f5k+1 + f5k) + f5k+1 = f5k+2 + 4f5k+1 + 2f5k = ( f5k+1 + f5k) + 4f5k+1 + 2f5k = 5 f5k+1 + 3f5k Since 5f5k+1 is a multiple of 5 (by definition) and f5k is a multiple of 5 (by hypoth- esis), so the right side is a multiple of 5. This proves that if P (k) is true, then P (k + 1) is true. Hence by Mathematical induction, we have proven: For each positive integer n, f5n is a multiple of 5. (b) For each positive integer n, f1 + f3 + · · ·+ f2n−1 = f2n. Solution: Let P (n) : f1 + f3 + · · ·+ f2n−1 = f2n Basis step: Let n = 1. Left side is just the term f1 and right side is f2. Since both f1 and f2 are 1, P (1) is true. Page 3

H3 Math (Mathematical Proofs and Reasoning) Problem Set 3 Inductive step: Assume P (k) is true. This means f1 + f3 + · · ·+ f2k−1 = f2k. Now add f2k+1 on both sides: f1 + f3 + · · ·+ f2k−1 + f2k+1 = f2k + f2k+1 f1 + f3 + · · ·+ f2k−1 + f2(k+1)−1 = f2k+2 = f2(k+1) This proves that if P (k) is true, then P (k + 1) is true. Hence by Mathematical induction, we have proven: For each positive integer n, f1 + f3 + · · ·+ f2n−1 = f2n. (c) For each positive integer n, 2fn + 3fn+1 = fn+4. Solution: Let P (n) : 2fn + 3fn+1 = fn+4. Basis step: P (1) and P (2) 2f1 + 3f2 = 2 + 3 = 5 = f5. So P (1) is true. 2f2 + 3f3 = 2 + 6 = 8 = f6. So P (2) is true. Inductive step: Assume P (k − 1) and P (k) are true. To show P (k + 1) is true. 2fk+1 + 3fk+2 = 2( fk−1 + fk) + 3(fk + fk+1) = (2 fk−1 + 3fk) + (2fk + 3fk+1) = fk+3 + fk+4 by P (k − 1) and P (k) of the induction hypothesis = fk+5 This proves that if P (k − 1) and P (k) are true, then P (k + 1) is true. Hence by Mathematical induction, we have proven: 2 fn + 3fn+1 = fn+4 for all n ∈ Z+. (d) For each positive integer n, fn is even if and only if 3 | n. Solution: The biconditional statement that can be rephrased as: (i) if 3 | n, then fn is even; (ii) if 3 ∤ n, then fn is odd. For (i), we let P (n) : fn is even. We shall use a variation of induction to prove P (n) for all n = 3h with h ∈ Z+. Basis step: P (3) is true, as f3 = 2 which is even. Inductive step: P (k) → P (k + 3). Assume fk is even. Then fk+3 = fk+2 + fk+1 = ( fk+1 + fk) + fk+1 = 2 fk+1 + fk Since both 2 fk+1 and fk are even, so fk+3 is even. Page 4

H3 Math (Mathematical Proofs and Reasoning) Problem Set 3 Hence, by PMI, fn is even for all n = 3h with h ∈ Z+. For (ii), we let P (n) : fn is odd. We shall use a variation of induction to proveP (n) for all n = 3h+ 1 andn = 3h+ 2 with h ∈ Z+ ∪ {0}. Basis step: P (1) and P (2) are true, as f1 = f2 = 1 which are odd. Inductive step: P (k) → P (k + 3). Assume fk is odd. Then fk+3 = fk+2 + fk+1 = ( fk+1 + fk) + fk+1 = 2 fk+1 + fk Since 2fk+1 is even and fk is odd, so fk+3 is odd. Hence, by PMI, fn is odd for all n = 3h + 1 and n = 3h + 2 with h ∈ Z+ ∪ {0}. 3. Use mathematical induction together with the following result: For any prime p and any integers a, b, if p | ab and p ∤ a, then p | b. prove that, for any prime p and any integers q1, q2, · · ·, qn, if p | q1q2 · · ·qn, then p | qi for some i. Solution: Let P (n): If p | q1q2 · · ·qn, then p | qi for some i. Basis step: P (1) is true, as the statement becomes: If p | q1, then p | qi for some i, and we can just take i = 1. Inductive step: P (k) → P (k + 1). Suppose p | q1q2 · · ·qk+1. If p | qk+1, then we are done. If p ∤ qk+1, by (*), we have p | q1 · · ·qk. By induction hypothesis, p | qi for some i. Hence we have proven the inductive step. By mathematical induction, the statement is proven for all integer n. 4. Suppose you want to prove P (n) is true (only) for all integersn ≥ 7 that are not divisible by 4 using a version of mathematical induction as follow: (i) Basis step: P (a), P(b), P(c) are true; and (ii) Inductive step: ( ∀ k ∈ Z+) P (k) → P (k + d) is true. What should be the values for a, b, c, d? Page 5

H3 Math (Mathematical Proofs and Reasoning) Problem Set 3 Solution: Explicitly, we want to prove P (n) for n = 7, 9, 10, 11, 13, 14, . . . Since we only want integers that are not divisible by 4, we only consider those integers that have remainders 1, 2, 3 modulo 4. So in the inductive step, we should have P (k) → P (k + 4), together with the basis step with three terms corresponding to remainders 1, 2 and 3. Since we require n ≥ 7, the three terms in the basis step should be 7 , 9, 10. Therefore, we have a = 7, b= 9, c= 10, d= 4. 5. Find the mistake in the following “proof” that purports to show that: Every nonnegative integer powe