Introduction to Mathematical Analysis I - Second Edition

17 Example 1.3.4 Prove by induction that 3 n < 2 n for all n ≥ 4. The statement is true for n = 4 since 12 < 16. Suppose next that 3 k < 2 k for some k ∈ N , k ≥ 4. Now, 3 ( k + 1 ) = 3 k + 3 < 2 k + 3 < 2 k + 2 k = 2 k + 1 , (1.1) where the second inequality follows since k ≥ 4 and, so, 2 k ≥ 16 > 3. This shows that P ( k + 1 ) is true. Thus, by the generalized principle of induction , the inequality holds for all n ≥ 4. Next we present another variant of the induction principle which makes it easier to prove the inductive step. Despite its name, this principle is equivalent to the standard one. Theorem 1.3.3 — Principle of Strong Induction. For each natural n ∈ N , 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) 1 ∈ A . (b) For each k ∈ N , if 1 , 2 , . . . , k ∈ A , then k + 1 ∈ A . Then A = N . Remark 1.3.4 Note that the inductive step above says that, in order to prove P ( k + 1 ) is true, we may assume not only that P ( k ) is true, but also that P ( 1 ) , P ( 2 ) ,. . . , P ( k − 1 ) are true. There is also a generalized version of this theorem where the base case is for some integer n 0 > 1. Example 1.3.5 Prove by induction that every positive integer greater than 1 is either a prime number or a product of prime numbers. Clearly, the statement is true for n = 2. Suppose the statement holds for any positive integer m ∈ { 2 , . . . , k } , where k ∈ N , k ≥ 2. If k + 1 is prime, the statement holds for k + 1. Otherwise, there are positive integers p , q > 1 such that k + 1 = pq . Since p , q ≤ k , by the inductive assumption applied to both p and q we can find prime numbers r 1 ,. . . , r ` and s 1 ,. . . , s m such that p = r 1 · · · r ` and q = s 1 · · · s m (note that ` and m may both equal 1). But then k + 1 = r 1 · · · r ` s 1 · · · s m . (1.2) Thus, the statement holds true for k + 1. The conclusion now follows by the Principle of Strong Induction. Exercises 1.3.1 Prove the following using Mathematical Induction. (a) 1 2 + 2 2 + · · · + n 2 = n ( n + 1 )( 2 n + 1 ) 6 for all n ∈ N . (b) 1 3 + 2 3 + · · · + n 3 = n 2 ( n + 1 ) 2 4 for all n ∈ N . (c) 1 + 3 + · · · +( 2 n − 1 ) = n 2 for all n ∈ N . 1.3.2 Prove that for all n ∈ N , 9 n − 5 n is divisible by 4. 1.3.3 Prove that for all n ∈ N , 7 n − 1 is divisible by 3.