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.