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.

If $n!=O(2^n)$, then there is a constant $c$ such that whenever $n>N$, then
$$n!\leq c\cdot 2^n$$
This means that whenever $n>N$, 
$$\frac{n!}{2^n}\leq c$$
This means that the sequence $$a_n=\frac{n!}{2^n}$$
is bounded.
Don't you smell something fishy? I give you $m=1234966785$. Can you find $n'$ such that $a_{n'}>m$? Can you do this for any $m$ I give you?
Note that 
$$a_n=\frac 1 2 \frac 2 2 \frac 3 2 \cdots \frac{n-1}{2}\frac n 2$$
Note that each term, except $\frac 1 2 $ greater or equal than $1$ for $n=1,2,\dots$ that is
$${a_n} = \frac{1}{2}\frac{2}{2}\frac{3}{2} \cdots \frac{{n - 1}}{2}\frac{n}{2} \geqslant \frac{1}{2}1 \cdot 1 \cdots 1 \cdot \frac{n}{2} = \frac{n}{4}$$
Then, this means $$b_n=\frac n 4 $$ is bounded. Do you see what's going on?
