To prove the inequality 3n ≤ n! for all integers n ≥ 3 using mathematical induction, we will follow these steps:
Base Case:
First, we need to verify the base case with n = 3:
- Left side: 3n = 3 × 3 = 9
- Right side: n! = 3! = 3 × 2 × 1 = 6
Clearly, 9 ≤ 6 is not true, so we will instead examine for n = 4:
- Left side: 3n = 3 × 4 = 12
- Right side: n! = 4! = 4 × 3 × 2 × 1 = 24
Now, we have 12 ≤ 24, which is true. Therefore, our base case holds for n = 4.
Inductive Step:
Assume the statement is true for some integer k ≥ 4; that is, we assume:
3k ≤ k!
We need to show that this implies:
3(k + 1) ≤ (k + 1)!
Starting from our inductive hypothesis:
- 3k ≤ k!
We want to manipulate the left side:
- 3(k + 1) = 3k + 3
Now, we need to show that:
3k + 3 ≤ (k + 1)! = (k + 1) × k!
Using our inductive hypothesis, we know that 3k ≤ k!, so:
- 3k + 3 ≤ k! + 3
Next, we need to prove that:
k! + 3 ≤ (k + 1) × k!
We can simplify the right side:
- (k + 1) × k! = k! + k!
Thus, we need to show:
3 ≤ k!
This is obviously true for all integers k ≥ 4 since 4! = 24. Hence, we can conclude:
3(k + 1) ≤ (k + 1)!
By the principle of induction, we have shown that 3n ≤ n! holds for all integers n ≥ 4.