University of Miami MTH 210230 solution manual 4

Chapter 4 Solutions An Introduction to Mathematical Thinking: Algebra and Number Systems William J. Gilbert and Scott A. Vanstone, Prentice Hall, 2005 Solutions prepared by William J. Gilbert and Alejandro Morales Exercise 4-1: Calculate the following. 5 3 Solution: 5 3 = 5 3 · · 4 2 · · 3 1 = 60 6 = 10. Exercise 4-2: Calculate the following. 10 6  Solution: 10 6  = 10 4  = 10 4 ··39··28··17 = 210 Exercise 4-3: Calculate the following. 8! (4!)2 Solution: 8! (4!)2 = 8 4 = 8 · 7 · 6 · 5 4 · 3 · 2 · 1 = 70. 4.1Exercise 4-4: Calculate the following. 100! − 99!. Solution: 100! − 99! = 99!(100 − 1) = (98!)(99)2 Exercise 4-5: Show that 1 nnr = 1r nr −− 11. Solution: For n, r ≥ 1, we have 1 n nr = n · r!(nn!− r)! = (n − 1)! r!(n − r)!, since n! = n(n − 1)!, n ≥ 1 = (n − 1)! r(r − 1)!(n − r)! = 1 r nr −− 11 establishing the result. Exercise 4-6: Show that nrrs = nsnr −− ss. Solution: nrrs = r!(nn−! r)! · s!(rr−! s)! = n! s!(n − r)!(r − s)! · (n − s)! (n − s)! = n! s!(n − s)! · (n − s)! (r − s)!((n − s) − (r − s))! = nsnr −− ss Exercise 4-7: Find n if n + 2 n  = 36. Solution: 4.2By definition, n + 2 n  = (n2! + 2)! n! . Hence, we must solve n2 + 3n + 2 = 72 or n2 + 3n + 70 = 0. By the quadratic formula, we find n = 7 or n = −10. Exercise 4-8: Write the following in sigma notation. 1 2 + 3 4 + 5 6 + · · · + 99 100 . Solution: 1 2 + 3 4 + 5 6 + · · · + 99 100 = 99 X r =1 r r + 1 . Exercise 4-9: Write the following in sigma notation. 8 + 15 + 24 + 35 + · · · + (n2 − 1). Solution: 8 + 15 + 24 + 35 + · · · + (n2 − 1) = nX r =3 (r2 − 1). Exercise 4-10: Write the following in sigma notation. ak + a2k + a4k + a8k + a16k + · · · + a256k Solution: ak + a2k + a4k + a8k + a16k + · · · + a256k = 8X r =0 a2rk. Exercise 4-11: Prove, by induction, the following results for all n ∈ P. 12 + 22 + 32 + · · · + n2 = n(n+1)(2n+1) 6 . Solution: (i) When n = 1 the assertion is true since 1(1+1)(2 6 ·1+1) = 6 6 = 1. 4.3(ii) Suppose that 12 + 22 + 32 + · · · + k2 = k(k + 1)(2k + 1) 6 . Then 12 + 22 + 32 + · · · + k2 + (k + 1)2 = k(k + 1)(2k + 1) 6 + 6(k + 1)(k + 1) 6 = (k + 1)(k(2k + 1) + 6(k + 1) 6 = (k + 1)(k(2k + 1) + 2(2k + 1) + 2(k + 2)) 6 = (k + 1)(k + 2)(2k + 1 + 2) 6 = (k + 1)(k + 2)(2(k + 1) + 1) 6 . Hence the assertion is true for n = k + 1. Therefore, by the principle of mathematical induction, the assertion is true for all n ∈ P. Exercise 4-12: Prove, by induction, the following results for all n ∈ P. 13 + 23 + 33 + · · · + n3 = n(n2+ 1)2 Solution: (i) If n = 1, then 13 = h1(1+1) 2 i2 . Hence the proposition is valid for n = 1. (ii) Assume that 13 + 23 + · · · + k3 = hk(k2+1)i2 for some k ∈ P. Then 13 + 23 + · · · + k3 + (k + 1)3 = k(k2+ 1)2 + (k + 1)3 = (k + 1)2 k4 2 + (k + 1) = (k + 1)2 k2 + 44k + 4 = (k + 1)2 (k + 2) 22 2 = (k + 1)( 2 k + 2)2 . Thus the proposition is valid for n = k + 1. Therefore, by the principle of mathematical induction, the proposition is true for all n ∈ P. Exercise 4-13: Prove by induction the following results for all n ∈ P. 14 + 24 + 34 + · · · + n4 = n(n + 1)(6n3 + 9n2 + n − 1) 30 4.4Solution: (i) For the base case n = 1, we have 14 = 1 and 1(2)(6+9+1 30 −1) = 30 30 = 1. Hence the formula is true when n = 1. (ii) As induction hypothesis, suppose that the formula holds when n = k, that is suppose 14 + 24 + 34 + · · · + k4 = k(k + 1)(6k3 + 9k2 + k − 1) 30 Then 14 + 24 + · · · + k4 + (k + 1)4 = k(k + 1)(6k3 + 9k2 + k − 1) 30 + (k + 1)4 = (k + 1)(6k3 + 9k2 + k − 1) + 30(k + 1)(k + 1)3 30 If we add and subtract 2(6k3 + 9k2 + k − 1) to the numerator it will have the terms (6k3 + 9k2 + k − 1)(k + 2)(k + 1) and (k + 1)30(k + 1)2 − 2(k + 1)(6k3 + 9k2 + k − 1) Working with these last two terms we have, (k + 1)(30k3 + 90k2 + 90k + 30 − 12k3 − 18k2 − 2k + 2) = (k + 1)(18k3 + 72k2 + 88k + 32) = (k + 1)(k + 2)(18k2 + 36k + 16) Putting the terms together we get 14 + 24 + 34 + · · · + k4 + (k + 1)4 = (k + 1)(k + 2)(6k3 + 9k2 + k − 1 + 18k2 + 36k + 16) 30 = (k + 1)(k + 2)(6k3 + 18k2 + 18k + 6) + 9k2 + 18k + 10 + k − 1
30 = (k + 1)(k + 2)6(k + 1)3 + (9k2 + 18k + 9) + (k + 1) − 1
30 = (k + 1)(k + 2)(6(k + 1)3 + 9(k + 1)2 + (k + 1) − 1) 30 . That is, the result is true for n = k + 1 whenever it is true for n = k. Therefore, by the Principle of Mathematical Induction, the result is true for all n ∈ P. 4.