Prove that $2^n = O(n!)$

Question

Do I have to use induction to prove this? I tried this:

Basis Step

$n = 1$

$2^1 = O(1!)$

$2 = O(1)$

This doesn't work and neither does 0.

Answer 1

Prove $2^n=O(n!)$

We must show

$\exists( M,x_0 \in \mathbb{R}) \text{ such that } \forall (n > x_0) (2^n \leq M n!) $

This is saying $Mn!$ is greater than or equal to $2^n$ for some real number M, for every $n$ greater than some other real number $x_0$.

Following the suggestion by Nicholas Stull in the comments above and your own suggestion of using induction, we can prove this for $M=1$ and $x_0 = 4$.

Basis : $2^4 = 16 < 24 = 4!$

Suppose it works for $k$, ie assume $2^k < k!$ for some $k$, and show it works for $k+1$

$2^{k+1} = 2(2^k) < (k+1)(2^k) < (k+1)k! = (k+1)!$