17 Then {k ∈N: k ≥n0} ⊂A. Proof: Suppose conditions (i) and (ii) hold. Assume, by way of contradiction, that the conclusion is false. That is, {k ∈N: k ≥n0}̸ ⊂A. Set B={n ∈N: n ≥n0 andP(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 (i), n0̸ ∈B. Hence, ℓ ≥n0 +1. It follows that k =ℓ−1≥n0. Since k < ℓ, k̸ ∈Band, so, we have that P(k) is true. By condition (ii), 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. □ ■ Example 1.3.4 Prove by induction that 3n<2 n for all n≥4. Let P(n) be the statement 3n<2n for n∈N, n≥4. P(n) is true for n=4 since 12<16. Suppose next that P(k) is true for some k ∈N, k ≥4. That is, 3k <2k for some k ∈N, k ≥4. Now, 3(k+1) =3k+3<2k +3<2k +2k =2k+1, where the second inequality follows since k ≥4 and, so, 2k ≥16>3. This shows that P(k+1) is true. Thus, by the Generalized Principle of Induction, 3n<2n 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: (i) 1∈A. (ii) For eachk ∈N, if 1,2, . . . ,k ∈A, then k+1∈A. Then A=N. Remark 1.3.1 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 condition (i) is replaced by n0 ∈A, for some integer n0 >1. We illustrate this theorem with the following example. ■ 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. Let P(n) be the statement nis either a prime number or a product of prime numbers, for n∈N, n≥2. Clearly, the statement is true for n=2. Suppose that P(2), P(3),. . . ,P(k) are true for some k ∈N, k ≥2. If k+1 is prime, then P(k+1) is true and the result follows. Otherwise, there are positive integers p,q>1 such that k+1=pq. Since p,q≤k, by the inductive assumption applied to both pandqwe can find prime numbers r1,. . . ,rℓ ands1,. . . ,smsuch that p=r1· · ·rℓ andq=s1· · ·sm (note that ℓ andmmay both equal 1). But then k+1=r1· · ·rℓs1· · ·sm. Thus, the statement holds true for k+1. The conclusion now follows by the generalized principle of strong induction.
RkJQdWJsaXNoZXIy NTc4NTAz