Prove that n! ext extgreater ext= 2ⁿ−1 for all n ext extgreater ext= 1.

Here is the proof using the Principle of Mathematical Induction.

10. Prove that $n! \ge 2^{n-1}$ for all $n \ge 1$.

Let $P(n)$ be the statement $n! \ge 2^{n-1}$.

• Base Case (n=1): LHS $= 1! = 1$ RHS $= 2^{1-1} = 2^0 = 1$ Since $1 \ge 1$, $P(1)$ is true.

• Inductive Hypothesis: Assume $P(m)$ is true for some positive integer $m$. That is, assume $m! \ge 2^{m-1}$.

• Inductive Step: We need to prove that $P(m+1)$ is true, i.e., $(m+1)! \ge 2^{(m+1)-1}$, which simplifies to $(m+1)! \ge 2^m$. Consider the LHS of $P(m+1)$:

  $$(m+1)! = (m+1) \cdot m!$$

  By the Inductive Hypothesis, we know $m! \ge 2^{m-1}$. Substitute this into the expression:

  $$(m+1)! \ge (m+1) \cdot 2^{m-1}$$

  Since $m \ge 1$, it follows that $m+1 \ge 2$. Therefore, we can write:

  $$(m+1) \cdot 2^{m-1} \ge 2 \cdot 2^{m-1}$$

  Simplify the right side:

  $$2 \cdot 2^{m-1} = 2^{1+(m-1)} = 2^m$$

  Combining the inequalities, we have:

  $$(m+1)! \ge (m+1) \cdot 2^{m-1} \ge 2^m$$

  Thus, $(m+1)! \ge 2^m$. This proves $P(m+1)$ is true.

By the Principle of Mathematical Induction, $P(n)$ is true for all $n \ge 1$.
The proof is complete.