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.

Comparing $\;2^n\;$ and $\;n!\;$

I need to rewrite one or the other so they can be more easily compared (i.e. have similar form). Because of the factorial, I'm a little lost as to how to compare the two functions. Normally, I would take the logarithm when trying to re-express a power like $2^n$, but I don't think this will work, since I don't know how to take the logarithm of a factorial, if at all.

Might the series expansions of either functions be the right approach? If not could, someone point me in the right direction?

share|improve this question
10  
Compute half a dozen terms, make a conjecture, prove it by induction. –  Git Gud May 28 '13 at 20:03
10  
You could use Stirling's approximation to get a better grip on that $n!$. But note that $$\frac{n!}{2^n} = \frac{n}{2} \times \frac{n-1}{2} \times \frac{n-2}{2} \times \dots \times \frac{2}{2} \times \frac{1}{2}.$$ So it should be clear which of the two is bigger... –  TMM May 28 '13 at 20:04
    
Very much related. –  1015 May 29 '13 at 1:12
1  
An interesting paper... –  J. M. May 30 '13 at 2:46
add comment

7 Answers

up vote 20 down vote accepted

$$2^n \;=\;\; \underbrace{\;2\cdot \;2 \;\cdot \; 2\; \cdot 2\cdot\;\; \ldots \;\;\cdot 2 \; \cdot \;2\;}_{\text{n $ $factors}}$$

$$n! = \underbrace{1\cdot 2\cdot 3 \cdot 4\cdot \ldots\cdot (n - 1)\cdot n}_{\text{n factors}}$$

When we compare the products $\,$ factor-by-factor,$\,$ we can easily see that when $n \geq 4$, $\;n!\;>\;2^n$.

This can, of course, be formalized using induction on $n$.

share|improve this answer
1  
^_^${}{}{}{}{}$ –  Git Gud May 28 '13 at 20:14
2  
@amWhy: Clean and visual +1 - hope it gets nice answer :-) –  Amzoti May 29 '13 at 0:31
    
Very nice amWhy! –  Sami Ben Romdhane Jan 14 at 13:17
add comment

Consider for $n \ge 4$: $$ 2^n = 2 \cdot 2 \cdot 2^{n - 2} < 2 \cdot 3 \cdot 4 \cdot \ldots \cdot n = n! $$

share|improve this answer
2  
:NOTICE FOR $n \ge 4$ –  Maisam Hedyelloo May 28 '13 at 20:06
3  
For $n=3$ we have $2^3=8$ and $3!=6$. –  Librecoin May 28 '13 at 20:08
    
@MaisamHedyelloo, (and Tharsis), thanks for noticing the slip. –  vonbrand May 28 '13 at 20:12
1  
Looks strange: $2^n \neq 2 \cdot 3 \cdot 2^{n-2}$ and if you fix it, the second inequality should hold for $n \geq 3$ not $n \geq 4$. –  gt6989b May 28 '13 at 20:25
1  
@gt6989b, you need $2 \cdot 2 \cdot 2 \cdot 2 < 1 \cdot 2 \cdot 3 \cdot 4$ to get going. –  vonbrand May 28 '13 at 22:24
add comment

Note that if $n\ge 2$ then $$\frac{2^n}{n!} =\left(\frac{2}{1}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots+\frac{2}{n-1}\right)\cdot\left(\frac{2}{n}\right)=\left(\frac{2}{2}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots+\frac{2}{n-1}\right)\cdot\left(\frac{4}{n}\right).$$ The product $\frac{2}{2}\cdot\frac{2}{2}\cdot\frac{2}{3}\cdots\frac{2}{n-1}$ is $\le 1$. It follows that $$\frac{2^n}{n!}\le \frac{4}{n}$$ when $n\ge 1$, and therefore $\frac{2^n}{n!}\to 0$ as $n\to\infty$.

share|improve this answer
add comment

By induction, $(n+1)!=(n+1) \cdot n! \geq (n+1) \cdot 2^n \geq 2 \cdot 2^n=2^{n+1}$ if $n! \geq 2^n$. Therefore, because $4$ is the smallest integer such that $2^n \leq n!$ is true, you deduce that $n! \geq 2^n$ for all $n \geq 4$.

share|improve this answer
3  
This is not true for $n\ge1$. –  Librecoin May 28 '13 at 20:15
3  
-1 until the initial condition is fixed. –  gt6989b May 28 '13 at 20:26
    
Indeed, but I supposed the initial condition was obvious. However, I fixed it to be clear. –  Seirios May 28 '13 at 22:31
    
@Seirios as promised, +1. –  gt6989b May 29 '13 at 2:14
add comment

\begin{align*} 2^n &= 2 \times 2 \times \dots \times 2 \times 2 \times 2 \\ n! &= 1 \times 2 \times \dots \times (n-2) \times (n-1) \times n \end{align*}

Both of these expressions are $n$ numbers multiplied together. So for $n < 4$, $2^n > n!$ because the 1 in $n!$ adds nothing. However, for $n \geq 4$, $n!$ will always be larger than $2^n$, because the 4 in $4!$ is $2 \times 2$ so it compensates for the extra 2 in $2^n$, and all other terms $3,5,6,7,\dots$ are all larger than $2$.

share|improve this answer
add comment

Normally, I would take the logarithm when trying to re-express a power like 2n, but I don't think this will work, since I don't know how to take the logarithm of a factorial, if at all.

$\log(n!) = \log(1) + \log(2) + \log(3) + ... + \log(n)$

You can approximate the sum by integrating the log function from 1 to $n$. Recall that the anti-derivative of the natural log is $x \ln{x} - x + C$. From this, you get log(n!) = O(n log n). Which is larger than $\log(2^n) = O(n)$.

If you're studying sorting algorithms in computer science, this is why comparison-based sorting algorithms (e.g., quicksort or mergesort) require O(n log n) time: These algorithm can be analyzed as a binary decision tree with $n!$ leaves (the possible permutations of the array). Taking the (base-2) logarithm gives you the depth of the tree (if it's balanced), which equals the number of comparisons required.

share|improve this answer
    
Meaning that while André Nicolas showed that $\frac{2^n}{n!} \to 0$, $\frac{\log (2^n)}{\log n!}$ diverges? –  dfeuer May 29 '13 at 0:36
    
No: $\frac{\log(2^n)}{\log {n!}} = \frac{O(n)}{O(n \log n)} = \frac{1}{\log n} → 0$ –  Dan Jun 23 '13 at 2:56
add comment

Method 1: You can take a graphical approach to this problem:

Factorial and 2 to the x

It can be seen that the graphs meet at (0, 1), $2^x$ is greater until they intersect when $x \approx 3.459$, and then the factorial becomes much greater. Alternatively, plot $x! - 2^x$ to see a demonstration of the difference.

Method 2: use Stirling's approximation,

$$x! \sim \left(\frac{x}{e}\right)^x\sqrt{2\pi{x}}\left(1 + \frac{1}{12x}\right)$$

Now you can take logarithms of both expressions. Comparing the graphs of $y = x$ and the base 2 logarithm of the above expression, it can be seen that the latter quickly rises above the former.

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.