4.2. Let P(n) be the claim that n! > 2n for all
integers n4.
P(4) is the statement: 4! > 24.
P(k) is the statement: k! > 2k.
P(k+1) is the statement: (k + 1)! > 2k+1.
For a proof by induction, you first need to check that the statement P(4) is true. Then assume that P(k) is true and use this to show that P(k + 1) is true.
The statement P(4) is true since 4! = 4·3·2·1 = 24 > 16 = 24.
Now assume that the statement P(k) is true. We now need to show that the left-hand side of P(k+1) is greater than the right-hand side of P(k+1).
| L.H.S. of P(k+1) | = | (k + 1)! |
| = | (k + 1) · k! | |
| > | (k + 1) · 2k (since we are assuming that P(k) is true, that is, k! > 2k) | |
| > | 2 · 2k ( we can assume that k is greater than 4 (our basis step) and so k + 1 > 2) | |
| = | 2k+1 | |
| = | R.H.S. of P(k+1) |
Therefore, for all integers n4,
n! > 2n.