Prove/disprove $n! = O(2^n)$ via mathematical induction

Question

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}

Answer 1

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

Answer 2

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.

Answer 3

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.