Prove/disprove $n! = O(2^n)$ via mathematical induction My computer science professor has us tasked with proving or disproving the statement $n! = O(2^n)$. We are then supposed to say if it's always true, always false, or non-conclusive (true in some cases but false in other cases).
So I believe that the statement $n! = O(2^n)$ is non-conclusive for the sole reason that it isn't true until $n\geq4$. I'm having a hard time proving the inductive step of my mathematical induction. Below is what I have so far, could someone help me out figure the induction step?

Problem $\boldsymbol 1$(c)
Is the statement True, False, or non-conclusive? Non-conclusive meaning true in some cases but false in other cases.
Question. $C(n) =n!$ implies that $C(n) =O(2^n)$ $\longleftarrow$ Prove or disprove
Given: $2^n \leq n!$
For $n=1$, we have $2^1 \leq 1! \implies 2\leq1$ which is FALSE.
For $n=2$, we have $2^2 \leq 2! \implies 4\leq2$ which is FALSE.
For $n=3$, we have $2^3 \leq 3! \implies 8\leq6$ which is FALSE.
For $n=4$, we have $2^4 \leq 4! \implies 16\leq24$ which is TRUE.
From pluging in some values we see that $n!$ seems to grow faster than $2^n$. Let's try and prove that through mathematical induction.
Let us suppose the following property $P(n)$ defined thusly: $$2^n \leq n! \quad \text{for all integers } n \geq 4.$$
Mathematical Induction Proof:
Step $1$. Prove the Basis step, we must show $P(4)$ is true. $$P(n) =2^n \leq n! \longrightarrow 2^4 \leq 4! \implies 16 \leq 24,$$ which is true.
Step $2$. Prove the inductive step, now suppose this works for any integer $k$, $k \leq 4$ such that $$2^k \leq k! \longleftarrow \text{inductive hypothesis}$$
Now to complete mathematical induction proof, we must show that the following is true for $P(k+1)$:
\begin{align}
2^{k+1} &\leq (k+1)! \\
(2^k)(2) &\leq (k+1)(k!)
\end{align}
 A: Hint: Stirling's approximation tells you $\log n! = n \log n - n + O(\log n)$ or that $n! \sim \sqrt{n} \left( n / e \right)^n$ where $\sim$ neglects a constant. 
Alternatively, assume $n! \in O(2^n)$. Then there would exists a constant $0 < k < \infty$ such that $n! \leq k 2^n$. Show something goes wrong with this for n larger than some $N$ (which is in terms of $k$). 
A: Outline: Divide $1\cdot 2\cdot 3\cdot 4\cdot 5\cdots n$ by $2\cdot 2\cdot 2\cdot 2\cdots 2$.
Since $\frac{4}{2}\ge 2$ and $\frac{5}{2}\ge 2$ and so on, for $n\ge 3$ the ratio is $\ge \frac{3}{2}2^{n-3}$.
If one feels like it, one can do this more formally by induction. The inequality holds at $n=3$, and the induction step is easy.
A: The statement
$n! = O(2^n)$
means that there is
a positive $c$
and a positive integer $N$
such that
$n! \le c 2^n$
for $n \ge N$,
or
$r(n)
=\frac{n!}{2^n}
\le c
$
for $n \ge N$.
Choosing
$n \ge \max(N, 4)$,
$r(n+1)
=\frac{(n+1)!}{2^{n+1}}
=\frac{n+1}{2}\frac{n!}{2^n}
>2r(n)
$.
By induction,
$r(n+k)
> 2^k r(n)
$
or
$r(n) 
<r(n+k)/2^k
< c/2^k
$.
Therefore
$r(n)$
can be made arbitrarily small,
which is a contradiction.
