Introduction to Mathematical Analysis I - 3rd Edition

16 1.3 The Natural Numbers and Mathematical Induction The statement P(n) is the equality 1+2+· · · +n=n(n+1) 2 for n∈N. Now the base case says that 1=1(1+1) 2 , which is clearly true. Suppose P(k) is true for some k ∈N. That is, suppose that 1+2+· · · +k =k(k+1) 2 for some k ∈N(this is the inductive hypothesis). Now we have 1+2+· · ·+k+(k+1) = k(k+1) 2 +(k+1) = k(k+1)+2(k+1) 2 = (k+1)(k+2) 2 . This shows that P(k+1) is true. We have now proved conditions (i) and (ii) of Theorem 1.3.1. Therefore, by the principle of mathematical induction we conclude that 1+2+· · ·+n= n(n+1) 2 for all n∈N. ■ Example 1.3.2 Prove using induction that 7 n −2n is divisible by 5 for all n∈N. The statement P(n) is 7n−2n is divisible by 5 for n∈N. For n=1, we have 7−2=5, which is clearly a multiple of 5. Therefore the base case is true. Suppose now that P(k) is true for some k∈N. That is, there is an integer j such that 7k −2k =5j. It follows that 7k =2k +5j. Now, substituting this expression below, we have 7k+1−2k+1 =7·7k−2·2k =7(2k+5j)−2·2k =7·2k−2·2k+7·5j =2k(7−2)+5·7j =5(2k+7j). Hence 7k+1 −2k+1 is a multiple of 5. This completes the proof of the inductive step. We conclude by induction that 7n −2n is divisible by 5 for all n∈N. ■ Example 1.3.3 Prove using induction that n+1≤2n for all n∈N. The statement P(n) is the inequality n+1≤2n for n∈N. For n=1, we have 1+1=2≤21, so the base case is true. Suppose next that P(k) is true for some that k ∈N. That is, k+1≤2k for some k ∈N. Then (k+1)+1≤2k +1. Since 2k is a positive integer, we also have 1≤2k. Therefore, (k+1)+1≤2k +1≤2k +2k =2· 2k =2k+1. This completes the proof of the inductive step. We conclude by the principle of mathematical induction that n+1≤2n for all n∈N. The following result is known as the Generalized Principle of Mathematical Induction. It simply states that we can start the induction process at any integer n0, and then we obtain the truth of all statements P(n) for n≥n0. Theorem 1.3.2 — Generalized Principle of Mathematical Induction. Let n0 ∈N and for each natural n ≥n0, suppose that P(n) denotes a proposition which is either true or false. Let A={n∈N: P(n) is true}. Suppose the following two conditions hold: (i) n0 ∈A. (ii) For eachk ∈N, k ≥n0, if k ∈A, then k+1∈A.

RkJQdWJsaXNoZXIy NTc4NTAz