# 證明$n！$不是$O（2 ^ n）$的矛盾

Since $m > n_0$:

$$m! \le c \cdot 2^m\qquad (m > n \ge n_0)$$

$$\ dfrac {m！} {c} \ le 2 ^ m$$

$$\ dfrac {1} {c} m！ \ le 2 ^ m$$

$$\dfrac{1}{m} m! \le 2^m\qquad (\text{as }m > c)$$

$$（m - 1）！ \ le 2 ^ m$$

## 最佳答案

It is quite easy to show that $n! \ge 3^n$ if $n\ge 7.$ If $n = 7$, we have $3^7 = 2187 < 5040 = 7!$. Now let $n\ge 7$.
$$n! = n\cdot(n-1)! \ge 3\cdot(n-1)! = 3\cdot 3^{n-1},$$ if we invoke the induction hypothesis $n! \ge 3^n$.
Then $${n!\over 2^n} \ge {3^n\over 2^n} \to \infty$$ as $n\to\infty$. This rules out $n! = O(2^n)$.