In: Advanced Math
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 as follows. 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 as follows. 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 natural number k, where k ≤ n, is in S, then n + 1 is in S. Using well-ordering, prove S = N.
Show, using mathematical induction, that 2k−1 ≤ k! for all natural numbers k, by doing parts (a) and (b).
(a) Let S be the set of natural numbers for which the inequality is true. Show that 1 is in S.
(b) Now conclude, using the induction hypothesis and the theorems 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.