n! is greater or equal to 2^n-1
prove by induction
To prove that n! is greater than or equal to 2^(n-1) using mathematical induction, we need to show the following two statements:
1. Base case: Show that the inequality holds true for n = 1.
2. Inductive step: Assume the inequality holds true for some arbitrary positive integer k, and then show that it also holds true for k + 1.
Let's go through the proof step-by-step:
1. Base case (n = 1):
When n = 1, we have:
1! = 1
2^(1-1) = 2^0 = 1
Since both sides of the inequality are equal to 1, the base case is true.
2. Inductive step (Assume it holds true for k):
Assume that for some positive integer k:
k! ≥ 2^(k-1)
Now, we need to prove that it also holds true for k + 1.
We need to show that (k + 1)! ≥ 2^k.
To prove this, we start with the left-hand side (LHS):
(k + 1)! = (k + 1) * k!
(k + 1)! = (k + 1) * (k! ≥ 2^(k-1)) [Using the assumption]
Now, let's consider the right-hand side (RHS):
2^k = 2^(k-1) * 2 [Since k * 2 = 2^k-1]
We need to show that (k + 1)! ≥ (k! ≥ 2^(k-1)) * 2.
Expanding the LHS and simplifying the RHS, we have:
(k + 1)! = k! * (k + 1) ≥ 2^(k-1) * 2 [Using the assumption]
It remains to show that k! * (k + 1) ≥ 2^(k-1) * 2.
Let's consider two cases:
Case 1: k + 1 < 2
In this case, k! * (k + 1) ≥ 2^(k-1) * 2 is automatically true as the RHS will be greater than the LHS.
Case 2: k + 1 ≥ 2
In this case, we can rewrite the inequality as:
k! * (k + 1) ≥ 2^k
Now, let's prove this by using the assumption:
k! * (k + 1) ≥ 2^(k-1) * 2 [Using the assumption]
k! * (k + 1) ≥ 2 * 2^(k-1) [Rearranging]
Since k + 1 ≥ 2, we can multiply both sides of the equation by (k + 1):
(k + 1) * k! * (k + 1) ≥ 2 * (k + 1) * 2^(k-1)
(k + 1)! ≥ 2 * (k + 1) * 2^(k-1)
Breaking down 2 * (k + 1) * 2^(k-1):
2 * (k + 1) = 2k + 2
2^(k-1) = 2 * 2^(k-1)
Hence, (k + 1)! ≥ 2 * (k + 1) * 2^(k-1) becomes:
(k + 1)! ≥ (2k + 2) * (2 * 2^(k-1))
(k + 1)! ≥ 2^(k-1) * 2k + 2^(k-1) * 2
Since 2k < 2^(k-1), we can simplify to:
(k + 1)! ≥ 2^k + 2^k
(k + 1)! ≥ 2^k + 2^k
(k + 1)! ≥ 2 * 2^k
(k + 1)! ≥ 2^k+1
Therefore, we have shown that if (k! ≥ 2^(k-1)), then it is also true for (k + 1), which completes the inductive step.
By proving the base case and the inductive step, we have shown that n! ≥ 2^(n-1) for all positive integers n by the principle of mathematical induction.