# Comparing $2^n$ to $n!$

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?

-
Compute half a dozen terms, make a conjecture, prove it by induction. –  Git Gud May 28 '13 at 20:03
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
An interesting paper... –  Guess who it is. May 30 '13 at 2:46

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

-
^_^${}{}{}{}{}$ –  Git Gud May 28 '13 at 20:14
@amWhy: Clean and visual +1 - hope it gets nice answer :-) –  Amzoti May 29 '13 at 0:31

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

-
:NOTICE FOR $n \ge 4$ –  Maisam Hedyelloo May 28 '13 at 20:06
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
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
@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

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

-

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

-
This is not true for $n\ge1$. –  Librecoin May 28 '13 at 20:15
-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

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.

-
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

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

-

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

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.

-