Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Take a look at the expansion $2 n!$ and compare it factor by factor to $2^n$. –  Fabian Apr 18 '12 at 8:05
add comment

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.