3
$\begingroup$

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

  • 0
    Take a look at the expansion $2 n!$ and compare it factor by factor to $2^n$.2012-04-18

3 Answers 3

6

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.

4

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.

  • 0
    That is the general idea, yes.2012-04-18
2

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