Exercise 2.2.5: Strong principle of induction
Contents Proposition Remark 1 Proof Proposition Let m 0 be a natural number. And let P ( m ) be a property pertaining to an arbitrary natural number m. Suppose that for each m ≥ m 0 , we have the following implication: if P ( m ′ ) is true for all natural numbers m 0 ≤ m ′ < m , then P ( m ) is also true. (In particular, this means that P ( m 0 ) is true, since in this case the hypothesis is vacuous.) Then we can conclude that P ( m ) is true for all natural numbers m ≥ m 0 . Remark 1 Since the principle of induction closes with a universal conclusion that the given property is true for all natural number x, we would intuitively apply it to the strong principle of induction because in the cases where x < m 0 , P ( x ) would be vacuously true. Whe...