Show that $2^n=O(n!)$ Show that $2^n=O(n!)$
Proof:
By definition of Big-O, $\exists$  constants $c$ and $n_0$ such that $2^n \le cn!$ $\forall  $ $n \ge n_0$. For a large $n$, since $$2^n = \underbrace{2 \cdot 2 \cdot 2\cdot\cdot\cdot2}_{n\text{ times}}$$ and  $$n! = 1 \cdot 2 \cdot 3 \cdot\cdot\cdot n$$ Clearly, as $n \rightarrow +\infty$ , $2^n \le cn!$.
Alternatively, WLOG, we use induction and show that $2^{n+1} \le c(n+1)!$.
$$2^n \le cn!$$
$$2^{n+1} \le 2(cn!) \le (cn+1)! \le c(n+1)! $$ since $cn+1 \ge 2.$
Question: Is my proof correct? and is there a better way of proving such. thanks
 A: Your proof is correct. Actually, it could be shown in the same way that $k^n = O(n!)$ for every $k$, and thus $k^n = o(N!)$ (because e.g. $k^n = o((2k)^n)$).
The easier proof is to show that, for $n > k$, $k^n &lt {n!}\frac{k!}{k^k}$: $k^n = k^k \times k^{n-k} &lt k^k \times ((k+1)(k+2) \ldots n) = k^k \times \frac{n!}{k!}$.
From the other hand, $n! = O(n^n)$, if you're interested.
A: You never state what $c$ is, and that is a weakness. Your first proof is too short, essentially stating the fact to be proven. But it can be fixed by multiplying together the $n-1$ inequalities $2\le k$ for $k=2,\ldots,n$.
Your second proof misses the start of the induction, and uses some rather mysterious looking inequalities.
Another way to proceed is to focus on $a_n=2^n/n!$ and estimating $a_{n+1}/a_n$. There are many ways to acieve what you need, but this one has the advantage of being applicable in many similar (and much less obvious) situations.
A: The idea behind both proofs is fine but the actual writing seems shaky, you need to provide actual values for c and $n_0$. For instance, in the first method you can use $n_0$ = 1 and c = 2, since 2(n!) = 2.2.3.4....n and here you can use a term-by-term comparison for all n$\ge$ 1.
For the induction proof, you could eg. take c = 1 and $n_0$ = 4. The induction step remains unchanged but you also need to show the base case that $2^4 \le 4!$.
