Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$

Question

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$

My attempt:

$f(n) = n!$
$g(n) = 2^n$

First I checked if I needed to prove or disprove this statement, and to do so I computed the $\lim_{n \to \infty}{\frac{f(n)}{g(n)}}$ = $\lim_{n \to \infty}{\frac{n!}{2^n}}$ which equals $\infty$ so this statement is false.

So to disprove it, I supposed that the statement was true. Then by the definition of big-oh, there would be a $C>0$ and $n_0 > 0$ such that $n! \leq C * 2^n $ for all $n \geq n_0$. So,

$$n! \leq C * 2^n $$ $$\frac{n!}{2^n} \leq C $$ $$2^{-n}n! \leq C $$

So we have constant $C \gt 0$ and $n_0 \geq 0$ such that $2^{-n}n! \leq C $.

But I don't think this can be possible since when looking at the values as n gets larger it increases:

$$\begin{array}{c|c|c|} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} \\ \hline \text{$2^{-n}n!$} & 0.5 & 0.5 & 0.75 & 1.5 & 3.75 \\ \hline \end{array}$$

Is this the correct way to approach this question and is my solution correct? Thank you to those who help.

Answer 1

Close to done - you still need to formalise the contradiction you're looking for. You've reduced it to showing that $a_n=\frac{n!}{2^n}$ isn't bounded, and indeed, it is not.

Noting that $a_n=\frac{n}{2}a_{n-1}$, we see that for $n\ge3$, $a_n\ge\frac{3}{2}a_{n-1}$, which gives that $a_n\ge \left(\frac{3}{2}\right)^{n-3}a_3$ by induction.

Hence, $a_n$ grows exponentially and thus is certainly not bounded, and your claim is proven.

Answer 2

What you have written down is not the claim you are trying to prove. It is the function $ n\mapsto n! $ itself that is not in $\mathcal{O}(n\mapsto 2^n) $, not each element of that function. (EDIT: As Qiaochu Yuan said in his comment)