# 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

-
Take a look at the expansion $2 n!$ and compare it factor by factor to $2^n$. –  Fabian Apr 18 '12 at 8:05

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 < {n!}\frac{k!}{k^k}$: $k^n = k^k \times k^{n-k} < 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.

-

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.

-
I think the constant $c$ for which it is large. With regards to $a_n$. Should I show that limit of $a_n$ approach to 0 as n approach positive infinity? –  Keneth Adrian Apr 18 '12 at 8:17
That is the general idea, yes. –  Harald Hanche-Olsen Apr 18 '12 at 12:47

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

-