5.2 MATHEMATICAL INDUCTION E PROVING FORMULAS 287 5. Fill in the missing pieces in the following proof 7. For every integer n 2 1, that 1+3+5+.--+(2-1)=m' 1+6+11+16+ + (50-4) = 2034-3) 2 for every integer n = 1. 8. For every integer # 2 0, Proof: Let the property P() be the equation 1 +2+2' 4..-+2" = 2"+l- 1. 1+3+5+ ... +(20-1)=N. -P(m] 9. For every integer n 2: 3, Show that P(1) is true: To establish P(1), we must show that when I is substituted in place of n, the 4' + 4+ + 45 + .+ 4" - _4(4" -16) left-hand side equals the right-hand side. But when 3 In = 1, the left-hand side is the sum of all the odd Prove each of the statements in 10-18 by mathematical integers from 1 to 2.1 - 1, which is the sum of the induction. odd integers from 1 to 1 and is just 1. The right-hand side is ", which also equals 1. So P(1) is true. 10. 1'+23+..+- a+ 1)(2+ 1) Show that for every integer & = 1, if P(K) is true 6 for every then Pik + 1) is true: Let & be any integer with integer m = 1. 71. 13 + 23+-- -+ "- (Suppose Pyk] is true. That is:] Suppose 2 . for every integer #21. 1+3+5+ ..+(24- 1) =_(b) 1 1 12. . . + (This is the inducrive hypothesis.] 1-2 2.3 : for every matl) atl' (We must show that P(k + 1) is true. That is:/ We integer n 2: 1. must show that 13. (c) = (d) 3 , for every integer Now the left-hand side of P(k + 1) is 1+3+5+ .+(2(*+1)-1) 14. "Si-2' = 1-2"+3+ 2, for every integer n 2 0. -1+3+5+ .. . + (2k + 1) by algebra = [1+3+5+ . +(2k- 1)] + (24+ 1) H 15. Said - (n + 1)! -1, for every integer n = 1. the next-to-last term is 24 - 1 because (e) - K + (2k+ 1) by Of) 16. 1-4 )- n+ 1 . for every - (k+ 1) by algebra, integer # 2 2. which is the right-hand side of P(k + 1) as was to be shown). W. II 18\\2/+ 1 21+2, (2n + 2)!' for every integer (Since we have proved the basis step and the induc- tive step, we conclude that the given statement is true.] Note: This proof was annotated to help make its 18. [1 1-= = = for every integer n 2 2. logical flow more obvious. In standard mathematic cal writing, such annotation is omitted. Hint: See the discussion at the beginning of this section. Prove each statement in 6-9 using mathematical induction. Do not derive them from Theorem 5.2.1 or 19. (For students who have studied calculus) Use Theorem 5.2.2. mathematical induction, the product rule from 6. For every integer n 2 1, calculus, and the facts that = = 1 and that *+1 = x x to prove that for every integer n = 1, 2+4+6+ ."+2=n'tn.288 CHAPTERS SEQUENCES, MATHEMATICAL INDUCTION, AND RECURSION Use the formula for the sum of the first n integers and/or Guess a general formula and prove it by matheman. the formula for the sum of a geometric sequence to evalu- cal induction. ate the sums in 20-29 or to write them in closed form. 20. 4+ 8 + 12+ 16+ -..+ 200 H 33. Find a formula in a, a, me, and a for the sum (a + md) + (a+ (m+ 1jd) + (a+(m +2)0)+ ...+ 21. 5+ 10 +15+ 20+ + 300 (a + (m + m)d), where m and a are integers, # 2 0, 22. a. 3+4+5+6+."+1000 and a and d are real numbers. Justify your answer. b. 3+4+5+6+ +m 34. Find a formula in a, 5 m, and a for the sum 23. a 7+8+9+10+ +600 b. 7+8 +9+10+."+k where in and a are integers, a 2 0, and a and r are 24. 1+2+3+ "