894 CHAPTER 12 Sequences; Induction; the Binomial Theorem 12.5 Mathematical Induction OBJECTIVE 1 Prove Statements Using Mathematical Induction (p. 894) 1 Prove Statements Using Mathematical Induction Mathematical induction is a method for proving that statements involving natural numbers are true for all natural numbers.* For example, the statement “the sum of the first n positive odd integers equals n ,2 ” that is, ( ) + + + + − = n n 1 3 5 2 1 2 (1) can be proved for all natural numbers n by using mathematical induction. Before stating the method of mathematical induction, let’s try to gain a sense of the power of the method. We use the statement in equation (1) for this purpose by restating it for various values of … n 1, 2, 3, . = = n 1 The sum of the first positive odd integer is = 1 ; 1 1 . 2 2 = n 2 The sum of the first 2 positive odd integers is 2 ;2 + = = 1 3 4 2 .2 = n 3 The sum of the first 3 positive odd integers is 3 ;2 + + = = 1 3 5 9 3 .2 = n 4 The sum of the first 4 positive odd integers is 4 ;2 + + + = = 1 3 5 7 16 4 .2 Although from this pattern we might conjecture that statement (1) is true for any natural number n, can we really be sure that it does not fail for some choice of n ? The method of proof by mathematical induction allows us to prove that the statement is true for all n. THEOREM The Principle of Mathematical Induction Suppose that the following two conditions are satisfied with regard to a statement about natural numbers: CONDITION I: The statement is true for the natural number 1. CONDITION II: If the statement is true for some natural number k, then it can be shown to be true for the next natural number + k 1. then the statement is true for all natural numbers. Using Mathematical Induction Show that the following statement is true for all natural numbers n. ( ) + + + + − = n n 1 3 5 2 1 2 (2) EXAMPLE 1 Figure 20 The following physical interpretation illustrates why the principle works. Think of a collection of natural numbers obeying a statement as a collection of infinitely many dominoes. See Figure 20. Now, suppose that two facts are given: 1. The first domino is pushed over. 2. If one domino falls over, say the k th domino, so will the next one, the ( ) + k 1 st domino. Is it safe to conclude that all the dominoes fall over? The answer is yes, because if the first one falls (Condition I), the second one does also (by Condition II); and if the second one falls, so does the third (by Condition II); and so on. *Recall that the natural numbers are the numbers 1, 2, 3, 4, . . . . In other words, the terms natural numbers and positive integers are synonymous.
RkJQdWJsaXNoZXIy NjM5ODQ=