1082 CHAPTER 11 Further Topics in Algebra Proofs of Statements Two separate steps are required for a proof by mathematical induction. Proof by Mathematical Induction Step 1 Prove that the statement is true for n = 1. Step 2 Show that, for any positive integer k, k … n, if Sk is true, then Sk+1 is also true. EXAMPLE 1 Proving an Equality Statement Let Sn represent the following statement. 1 + 2 + 3 + g+ n = n1n + 12 2 Prove that Sn is true for every positive integer n. SOLUTION Step 1 Show that the statement is true when n = 1. If n = 1, S1 becomes 1 = 111 + 12 2 , which is true. Step 2 Show that Sk implies Sk+1, where Sk is the statement 1 + 2 + 3 + g+ k = k1k + 12 2 , and Sk+1 is the statement 1 + 2 + 3 + g+ k + 1k + 12 = 1k + 1231k + 12 + 14 2 . Start with Sk and assume it is a true statement. 1 + 2 + 3 + g+ k = k1k + 12 2 Add k + 1 to each side of this equation to obtain Sk+1. 1 + 2 + 3 + g+ k + 1k + 12 = k1k + 12 2 + 1k + 12 Add k + 1 to each side. = 1k + 12 a k 2 + 1b Factor out k + 1 on the right. = 1k + 12 a k + 2 2 b Add inside the parentheses. 1 + 2 + 3 + g+ k + 1k + 12 = 1k + 12 31k + 12 + 14 2 Multiply; k + 2 = 1k + 12 + 1 This final result is the statement for n = k + 1. It has been shown that if Sk is true, then Sk+1 is also true. The two steps required for a proof by mathematical induction have been completed, so the statement Sn is true for every positive integer value of n. S Now Try Exercise 7. This is the statement Sk+1.
RkJQdWJsaXNoZXIy NjM5ODQ=