1081 11.5 Mathematical Induction A proof by mathematical induction can be explained as follows. By assumption (1) above, the statement is true when n = 1. By assumption (2) above, the fact that the statement is true for n = 1 implies that it is true for n = 1 + 1 = 2. Using (2) again, the statement is thus true for 2 + 1 = 3, for 3 + 1 = 4, for 4 + 1 = 5, and so on. Continuing in this way shows that the statement must be true for every positive integer. The situation is similar to that of an infinite number of dominoes lined up as suggested in Figure 12. If the first domino is pushed over, it pushes the next, which pushes the next, and so on continuing indefinitely. The truth of this statement is easily verified for the first few values of n. If n = 1, then S1 is 1 = 111 + 12 2 . This is true because 1 = 1. If n = 2, then S2 is 1 + 2 = 212 + 12 2 . This is true because 3 = 3. If n = 3, then S3 is 1 + 2 + 3 = 313 + 12 2 . This is true because 6 = 6. If n = 4, then S4 is 1 + 2 + 3 + 4 = 414 + 12 2 . This is true because 10 = 10. We cannot conclude that the statement is true for every positive integer n simply by observing a finite number of examples. To prove that a statement is true for every positive integer value of n, we use the following principle. Another example of the principle of mathematical induction is the concept of an infinite ladder. Suppose the rungs are spaced so that whenever we are on a rung, we know we can move to the next rung. Then if we can get to the first rung, we can go as high up the ladder as we wish. Figure 12 Principle of Mathematical Induction Let Sn be a statement concerning the positive integer n. Suppose that both of the following are satisfied. 1. S1 is true. 2. For any positive integer k, k … n, if Sk is true, then Sk+1 is also true. Then Sn is true for every positive integer value of n.
RkJQdWJsaXNoZXIy NjM5ODQ=