Introduction to Mathematical Analysis I - Second Edition

16 1.3 THE NATURAL NUMBERS AND MATHEMATICAL INDUCTION Suppose P ( k ) is true for some k ∈ N . That is, suppose that 1 + 2 + · · · + k = k ( k + 1 ) 2 (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 (a) and (b) 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 for all n ∈ N , 7 n − 2 n is divisible by 5. For n = 1, we have 7 − 2 = 5, which is clearly a multiple of 5. Suppose that 7 k − 2 k is a multiple of 5 for some k ∈ N . That is, there is an integer j such that 7 k − 2 k = 5 j . Let us write 7 k = 2 k + 5 j . Now, substituting this expression below, we have 7 k + 1 − 2 k + 1 = 7 · 7 k − 2 · 2 k = 7 ( 2 k + 5 j ) − 2 · 2 k = 7 · 2 k − 2 · 2 k + 7 · 5 j = 2 k ( 7 − 2 )+ 5 · 7 j = 5 ( 2 k + 7 j ) . It follows that 7 k + 1 − 2 k + 1 is a multiple of 5. This proves the inductive step. We conclude by induction that 7 n − 2 n is divisible by 5 for all n ∈ N . Example 1.3.3 Prove using induction that for all n ∈ N n + 1 ≤ 2 n For n = 1, we have 1 + 1 = 2 = 2 1 , so the base case is true. Suppose next that k + 1 ≤ 2 k for some k ∈ N . Then k + 1 + 1 ≤ 2 k + 1. Since 2 k is a positive integer, we also have 1 ≤ 2 k . Therefore, ( k + 1 )+ 1 ≤ 2 k + 1 ≤ 2 k + 2 k = 2 · 2 k = 2 k + 1 . We conclude by the principle of mathematical induction that n + 1 ≤ 2 n 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 n 0 , and then we obtain the truth of all statements P ( n ) for n ≥ n 0 . Theorem 1.3.2 — Generalized Principle of Mathematical Induction. Let n 0 ∈ N and for each natural n ≥ n 0 , 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: (a) n 0 ∈ A . (b) For each k ∈ N , k ≥ n 0 , if k ∈ A , then k + 1 ∈ A . Then { k ∈ N : k ≥ n 0 } ⊂ A . Proof: Suppose conditions (a) and (b) hold. Assume, by way of contradiction, that A 6⊇ { k ∈ N : k ≥ n 0 } . Set B = { n ∈ N : n ≥ n 0 , P ( n ) is false } . Then B is a nonempty subset of N . By the Well- Ordering Property of the natural numbers, there exists a smallest element ` ∈ B . By condition (a), n 0 6∈ B . Hence, ` ≥ n 0 + 1. It follows that k = ` − 1 ≥ n 0 . Since k < ` , k 6∈ B and, so, we have that P ( k ) is true. By condition (b), we obtain that P ( k + 1 ) is true. But k + 1 = ` , and P ( ` ) is false, since ` ∈ B . This is a contradiction, so the conclusion follows.