4
$\begingroup$

I am having issues with this proof: Prove by contradiction that $n! \ne O(2^n)$. From what I understand, we are supposed to use a previous proof (which successfully proved that $2^n = O(n!)$) to find the contradiction.

Here is my working so far:

Assume $n! = O(2^n)$. There must exist $c$, $n_{0}$ such that $n! \le c \cdot 2^n$. From the previous proof, we know that $n! \le 2^n$ for $n \ge 4$.

We pick a value, $m$, which is gauranteed to be $\ge n_{0}$ and $\ne 0$. I have chosen $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$$

That's where I get up to.. not sure which direction to head in to draw the contradiction.

  • 0
    Induction to prove that your last inequality is false from some $m$ onwards.2012-07-29
  • 0
    The sentence starting, "from a previous proof..." has the inequality wrong.2012-07-29

6 Answers 6