Proof by contradiction that $n!$ is not $O(2^n)$ 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.

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