The integers satisfy a property known as mathematical induction.This is a familiar topic in high school textbooks.
(a) The First Principle of Mathematical Induction is stated asfollows. Suppose S is a subset of N with the following properties:(i) The number 1 is in S. (ii) If n is in S, then n + 1 is in S.Using well-ordering, prove S = N.
(b) The Second Principle of Mathematical Induction is stated asfollows. Suppose S is a subset of N with the following properties:(i) The number 1 is in S. (ii) If n is in S and if every naturalnumber k, where k ? n, is in S, then n + 1 is in S. Usingwell-ordering, prove S = N.
Show, using mathematical induction, that 2k?1 ? k! for allnatural numbers k, by doing parts (a) and (b).
(a) Let S be the set of natural numbers for which the inequalityis true. Show that 1 is in S.
(b) Now conclude, using the induction hypothesis and thetheorems about inequalities, that 2 n = 2 · 2 n?1 ? 2 · n! ? (n +1) · n! = (n + 1)! That is, if n is in S, then n + 1 is in S.
