|
Question 872853: Please help me solve this induction question using a direct proof:
Prove by induction that n! < n^n, for positive integers n >= 2
Answer by jim_thompson5910(35256)   (Show Source):
You can put this solution on YOUR website! First prove the base case n = 2.
n! < n^n
2! < 2^2
2 < 4 ... true
Inductive Step:
Assume the n = k case is true. So assume
k! < k^k
is true. We must prove the n = k+1 case is true based on the assumption n = k.
So start with k! < k^k and multiply both sides by k+1
k! < k^k
(k+1)*k! < (k+1)*k^k
The inequality is still true because k+1 is positive (n >= 2, so k > 2). So the inequality sign has NOT flipped. It only flips when we multiply both sides by a negative number.
Now if we replace the base 'k', of k^k on the right side, with 'k+1', we get
(k+1)*k! < (k+1)*k^k
(k+1)*k! < (k+1)*(k+1)^k
(k+1)*k! < (k+1)^1*(k+1)^k
(k+1)*k! < (k+1)^(1+k)
(k+1)*k! < (k+1)^(k+1)
(k+1)! < (k+1)^(k+1)
This last inequality is certainly true because (k+1)*k! < (k+1)*k^k is true and (k+1)^k is larger than k^k.
That means (k+1)*(k+1)^k is larger than (k+1)*k^k.
By extension, this means (k+1)*(k+1)^k is larger than (k+1)*k!
So the right side is still larger than the left side. That's all we care about.
So to wrap things up we assumed the equation held true for the n = k case. Then we just showed that the n = k+1 case is true based on the assumption that the inequality holds true when n = k.
This inductive step proves n! < n^n is true for all integers n >= 2.
|
|
|
| |
