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 &gt; n_0$:

$$m! \le c \cdot 2^m\qquad (m &gt; 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 &gt; c)$$

$$(m - 1)! \le 2^m$$

That's where I get up to.. not sure which direction to head in to draw the contradiction.
In 
Factorial Inequality problem $\left(\frac n2\right)^n &gt; n! &gt; \left(\frac n3\right)^n$,
they have obtained
$$
n!\geq \left(\frac{n}{e}\right)^n.
$$
Hence 
$$
\lim_{n\rightarrow\infty}\frac{n!}{2^n}\geq\lim_{n\rightarrow\infty}\left(\frac{n}{2e}\right)^n=\infty.
$$
Suppose that $n!=O(2^n)$. Then there exist $C&gt;0$ and $N_0\in \mathbb{N}$ such that 
$$\frac{
n!}{2^n}\leq C
$$
for all $n\geq N_0$. Lettting $n\rightarrow\infty$ in the aobve inequality we obtain
$$
\lim_{n\rightarrow\infty}\frac{n!}{2^n}\leq C,
$$
which is an absurd.
This is the cleanest proof I can think of:

Using the same techniques used to show $2^n=O(n!)$, we can show that $3^n = O(n!)$ as well.  If we had $n!=O(2^n)$, then this implies $3^n = O(2^n)$, contradiction.