一千萬個為什麽

搜索

證明$ n!$不是$ O(2 ^ n)$的矛盾

我有這個證據的問題:證明矛盾,$ n! \ ne O(2 ^ n)$。根據我的理解,我們應該使用先前的證明(成功證明$ 2 ^ n = O(n!)$)來找到矛盾。

這是我到目前為止的工作:

假設$ n! = O(2 ^ n)$。必須存在$ c $,$ n_ {0} $這樣的$ n! \ le c \ cdot 2 ^ n $。從之前的證明,我們知道$ n! \ le 2 ^ n $ for $ n \ ge 4 $。

我們選擇一個價值$ m $,這個價值是$ \ ge n_ {0} $和$ \ ne 0 $。我選擇了$ m = n_ {0} + 10 + c $。

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)$.

轉載註明原文: 證明$ n!$不是$ O(2 ^ n)$的矛盾