MOE H3 Math Proofs and Reasoning Problem Set 3

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. (b) For each positive integer n, (−7)n − 9n is divisible by 16. (c) For each positive integer n with n ≥ 3,

1 + 1 n n < n. (d) For each positive integer n with n ≥ 6, n3 < n!. 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. (b) For each positive integer n, f1 + f3 + · · ·+ f2n−1 = f2n. (c) For each positive integer n, 2fn + 3fn+1 = fn+4. (d) For each positive integer n, fn is even if and only if 3 | n. 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. 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? 5. Find the mistake in the following “proof” that purports to show that: Every nonnegative integer power of every nonzero real number is 1.

H3 Math (Mathematical Proofs and Reasoning) Problem Set 3 Proof. Let r be any nonzero real number and let the predicate P (n) be P (n) : rn = 1. Basis step: P (0) is true because r0 = 1 by definition of 0-th power. Inductive step: P (k − 1) and P (k) → P (k + 1) Suppose that rk−1 = 1 and rk = 1. This is the induction hypothesis. We must show that rk+1 = 1. Now rk+1 = rk+k−(k−1) = rk · rk rk−1 = 1 · 1 1 (by induction hypothesis) = 1 Thus rk+1 = 1. Hence the inductive step is proven. 6. Prove that for integers n ≥ 2, nY i=2

1 − 1 i2

= n + 1 2n . 7. Suppose x is a real number with x ̸= 0 and x + 1 x ∈ Z. Prove by induction on n that xn + 1 xn ∈ Z for all n ∈ Z>0. 8. Prove that for positive integers n and positive real numbers x1, . . . , xn, 1 n nX i=1 xi ≥ nY i=1 xi !1/n . First prove the statement for n = 2m for m ≥ 0 by induction on m. The general result now follows by proving the converse of the usual inductive step: if the result holds for n = k + 1, where k is a positive integer, then it holds for n = k. Page 2

H3 Math (Mathematical Proofs and Reasoning) Problem Set 3 Hints 1. Hint for Question 1. (a) In the inductive step, add an additional term to both sides of P (k). (b) In the inductive step, multiply 9 to both sides of P (k). (c) Basis step is n = 3. You need to use the inequality

1 + 1 k + 1 k+1 <

1 + 1 k k+1 in the inductive step. (d) Basis step is n = 3. You need to use the inequality ( k + 1)2 ≤ k3 for k ≥ 3 in the inductive step. 2. Hint for Question 2. (a) Let P (n) be the predicate ‘f5n is a multiple of 5’. In the induc- tive step, try to show f5(k+1) = 5f5k+1 + 3f5k. (Use the recursive relation of Fibonacci sequence.) (b) In the inductive step, P (k) : f1 + f3 + · · ·+ f2k−1 = f2k. Add f2k+1 to both sides of P (k). (c) Prove P (1) and P(2) in the basis step; and use P (k − 1) and P (k) in the induction hypothesis. (d) Note that this is a biconditional statement that can be rephrased as: (i) if 3 | n, then fn is even; (ii) if 3 ∤ n, then fn is odd. For each case, use a variation of PMI to prove it. The inductive step should be P (k) → P (k + 3). 3. Hint for Question 3. Use PMI on the number of terms in the product. 4. Hint for Question 7. Use Principle of Strong Induction. For the inductive step consider

xk + 1 xk x + 1 x

. 5. Hint for Question 8. Assuming statement holds for n = 2 m, to show that statement holds for 2 m+1, define yj = x2j−1 + x2j 2 (1 ≤ j ≤ 2m). Use the n = 2 case to show that yj ≥ (x2j−1x2j)1/2. To extend beyond powers of two, assume AM ≥GM holds for some k + 1 ≥ 2. For x1, . . . , xk > 0, let A = 1 k kX i=1 xi. Apply the k + 1 case to x1, . . . , xk, A. Page 3