53
$\begingroup$

Someone asked me this question, and it bothers the hell out of me that I can't prove either way.

I've sort of come to the conclusion that 20! must be larger, because it has 36 prime factors, some of which are significantly larger than 2, whereas $2^{40}$ has only factors of 2.

Is there a way for me to formulate a proper, definitive answer from this?

Thanks in advance for any tips. I'm not really a huge proof-monster.

$\endgroup$
  • 2
    $\begingroup$ There are $[n/2]+[n/2^2]+[n/2^3]+\dots =\sum_{k\geq 1}[n/2^k]$ factors of $2$ in $n!$. Where [$a$] is the floor function, i.e. greatest integer less than $a$. Combining this fact with some estimation of the other primes dividing $20!$ you should be able to get the result. $\endgroup$ – mojambo Nov 11 '13 at 15:12
  • 1
    $\begingroup$ Your "sort of" conclusion becomes a proof if you observe that at least 4 of those prime factors are at least twice as large as 2. $\endgroup$ – Dan Nov 13 '13 at 22:50

16 Answers 16

177
$\begingroup$

It is probably easier to note that $2^{40} = 4^{20}$. The only ones of the 20 factors in $20!$ that are smaller than $4$ are $1$, $2$ and $3$. But, on the other hand, $18$, $19$ and $20$ are all larger than $4^2$, so we can see $$ 20! = 1\cdot 2\cdot3\cdots 18\cdot19\cdot 20 > \underbrace{1\cdot1\cdot1}_{3\text{ ones}}\cdot\underbrace{4\cdot4\cdots 4\cdot 4}_{14\text{ fours}}\cdot\underbrace{16\cdot16\cdot 16}_{3\text{ sixteens}} = 2^{40} $$ by comparing factor by factor.

$\endgroup$
  • $\begingroup$ +1, but $$1\cdot1\cdot1\cdot4\cdot4\cdots 4\cdot 4\cdot16\cdot16\cdot 16 =2^{24} \cdot 2^{12} \lt 2^{40}$$ Better $$1\cdot1\cdot1\cdot4\cdot4\cdots 4\cdot 4\cdot16 \cdots \cdot 16 = 2^{44} \gt 2^{40}$$ $\endgroup$ – miracle173 Nov 11 '13 at 15:27
  • 17
    $\begingroup$ @miracle173: I think your arithmetic's off. How do you get $4^{14}$ to be $2^{24}$? $\endgroup$ – Henning Makholm Nov 11 '13 at 15:31
  • 8
    $\begingroup$ because you added the braces after you read my comment. I assumed that $16 \cdot 16 \cdot 16$ was a lower bound for $16 \cdot 17 \cdots$ and $4 \cdot 4 \cdot 4 \cdots 4 \cdot 4$ is a lower bound for $4 \cdot 5 \cdot 6 \cdots 15$. $\endgroup$ – miracle173 Nov 12 '13 at 6:42
81
$\begingroup$

You can simply compute both numbers and compare them: $$ 20! = 2432902008176640000 \\ 2^{40} = 1099511627776 $$

So you can easily see that $2^{40} < 20!$

$\endgroup$
  • 6
    $\begingroup$ I would not be surprised if this answer was in negative votes. $\endgroup$ – N.S.JOHN Apr 27 '16 at 8:11
  • 3
    $\begingroup$ I can't believe that this answer received 81 upvotes. $\endgroup$ – Zephyr Oct 9 '17 at 9:18
  • 1
    $\begingroup$ It seems this answer has gotten a lot of votes in both directions. But I, the asker, should have been more clear. Although I was looking for something more... elegant... I didn't specify this, so as it stands, this is a perfectly acceptable answer, and it has my upvote. $\endgroup$ – Alec Mar 24 '18 at 17:31
50
$\begingroup$

Use a multiplicative variant of Gauss's trick: $$ (n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n $$ Setting $n=20$, we get $20!\ge 20^{10} > 16^{10} = 2^{40}$.

$\endgroup$
  • 2
    $\begingroup$ It's worth adding how you know that $k(n-k+1)\ge n$. $\endgroup$ – nbubis Feb 24 '17 at 18:39
43
$\begingroup$

Well we know that $\log_2 x$ is increasing so we could calculate

$$\begin{align} \log_2(20!) &=\log_2\left(\prod_{i=1}^{20}i\right) \\ &=\sum_{i=1}^{20}\log_2(i) \\ &=\log_2{1}+\log_2{2}+\log_23+\log_2{4}+\cdots+\log_2 8+\cdots+\log_216+\cdots+\log_2{20} \\ &>0+\log_2{2}+\log_2 2+\log_24+\cdots+\log_2{4}+ \\&\,\,\,\,\,\log_28+\cdots+\log_2{8}+\log_2{16}+\cdots+\log_2{16} \\ &=0+2\log_2{2}+4\log_2{4}+8\log_2{8}+5\log_2{16} \\&=0+2+4 \cdot 2+8 \cdot 3+5 \cdot 4 \\&=54 \\&>40=\log_2(2^{40}). \end{align}$$

Therefore, as $\log_2x$ is increasing we have $20!>2^{40}$.

In fact this shows that $20!>2^{54}$.

$\endgroup$
30
$\begingroup$

$$\frac{(20)!}{2^{40}}=\frac{(20)!}{4^{20}}=\frac14\cdot\frac24\cdot\frac34\cdot\frac44\cdots\frac{19}4\cdot\frac{20}4>\frac{3!}{4^3}\cdot\frac{19}4\cdot\frac{20}4=\frac{6\cdot19\cdot5}{64\cdot4}=\frac{570}{256}>1$$

That was a defensive approach

Observe that $\displaystyle\frac14\cdot\frac24\cdot\frac34=\frac3{32}>\frac1{11}$ which is compensated by $\displaystyle\frac84\frac94\cdot\frac{10}4=\frac{45}4>11$

$$\implies \frac{(20)!}{2^{40}}=\frac14\cdot\frac24\cdot\frac34\cdot\frac44\cdots\frac{19}4\cdot\frac{20}4>\frac14\cdot\frac24\cdot\frac34\cdots \frac84\frac94\cdot\frac{10}4>\frac1{11}\cdot\frac{45}4>1$$

i.e., $$\frac{(20)!}{4^{20}}> \frac{(10)!}{4^{10}}>1 $$

Programmatically, I found $\displaystyle \frac{n!}{4^n}>1$ for $n\ge9$ which I think can be a good exercise

$\endgroup$
27
$\begingroup$

If we ignore the first terms of $20!$ we have $8 \times \dots \times 20$. That's at the very least $8^{13}$, which is $2^{39}$. Including the first factors we ignored we go over $2^{40}$.

Pretty ad-hoc, but just my 2 cents.

$\endgroup$
16
$\begingroup$

It is easy to compare these numbers using some basic analysis.

To approximate the numeric value of $20!$, use Stirling formula, which says that $20! \simeq (20/e)^{20} \sqrt{40 \pi}$. The usage of $\simeq$ here is a little vague; what the theorem actually says is that the ratio of the two is between $1$ and $1.08...$, which is more than enough for this application. Now, $20/e \simeq 7.35 \gg 4 = 2^2$, and the additional factor is greater than $1$, so you get: $$20! \gg (20/e)^{20} \gg 4^{20} = 2^{40}.$$

The sign $\gg$ is used a bit informally to mean 'is much greater than'. Feel free to replace it by simply $>$ if you like.

$\endgroup$
  • 3
    $\begingroup$ How do you know that Stirling's approximation works well for $n$ as low as $20$? $\endgroup$ – lhf Nov 11 '13 at 15:16
  • 3
    $\begingroup$ @lhf: the error in Stirling formula is bounded as explained in the edit. $\endgroup$ – Jakub Konieczny Nov 11 '13 at 15:20
  • 3
    $\begingroup$ @lhf: also, Stirling's approximation offers a lower bound on $n!$, so showing that $(20 / e)^{20} > 4^{20}$ is enough to show that $20! > 4^{20}$. $\endgroup$ – hunse Nov 11 '13 at 20:56
9
$\begingroup$

From your statement that you know $20!$ has $36$ prime factors, you just need to note that there are four $5$'s and two $7$'s among them. Since $7 \gt 5\gt 2^2$ you have the four extra you need and are done.

$\endgroup$
9
$\begingroup$

I know I am beating a dead horse here, but anyways. If you can accept some "handwaving" this is an argument a normal higschool student should be able to accept. We have that if $a>b$ then $\log a > \log b$. Now when comparing big numbers, it is often easier to look at the logarithms. The crux here is to note that $$ \log 20! > 20 \log(20)-20 $$ Let us assume that $20!<2^{40}$, and see if we obtain a contradiction. \begin{align*} \log 2^{40} & > 20 \log(20)-20\\ 40 \log 2 & > 20(\log 5 + 2\log2)-20\\ 0 & > 20 \log 5 - 20 \\ 1 & > \log 5 \end{align*} Which is rubbish since $\log 5 > \log e = 1$. Therefore $$ 20! > 2^{40} $$ To see that $$ \log n! > n \log n - n \ , \quad \forall \, n>0 $$ One can note that $$ \log n! = \sum_{k=1}^n \log k > \int_1^n \log x\,\mathrm{d}x = n \log n - n $$ Where the inequality comes from the following figure

Riemansum

$\endgroup$
  • $\begingroup$ @dfeuer, I updated the figure it should be correct now =) $\endgroup$ – N3buchadnezzar Nov 12 '13 at 19:57
  • $\begingroup$ Nice solution using Graph. $\endgroup$ – juantheron Nov 13 '13 at 4:44
8
$\begingroup$

You can also separate each one of these, into 10 terms and note:

$$1\times 20 > 2^4$$ $$2\times 19 > 2^4$$ $$\vdots$$ $$10 \times 11 >2^4$$ $$\Rightarrow 20! > 2^{40}$$

The idea is to break the factorial symmetrically into smaller pieces; which is not the most robust method for inequalities which include factorials; but it is useful in certain obvious cases.

$\endgroup$
  • $\begingroup$ lhf did exactly this above. $\endgroup$ – JP McCarthy Nov 11 '13 at 21:49
3
$\begingroup$

$2^{40}= (2^{10})^4 = 1024^4 \approx (10^3)^4 = 10^{12}$

$20! = (20 \cdot 19 \cdot 18 \cdots 10) \cdot 9 \cdot 8\cdots 1 > 10^{11} \cdot 9 \cdot 8 \cdots 1 \gg 10^{12}$

$\endgroup$
2
$\begingroup$

By calculator you can see that $10! > 2^{20}$.
It is then easy to prove that for any $n >= 10$ that $n! > 2^{2n}$.
For intuitive purposes, just remember that on the left hand side you are multiplying by a growing number (larger than 10) and on the right hand side you are multiplying by 4.

$\endgroup$
1
$\begingroup$

Here's my take on this:

First find the number of factors of 2 in 20! This can be done with

$\left\lfloor \frac{20}{2^{1}} \right\rfloor\; \; +\; \left\lfloor \frac{20}{2^{2}} \right\rfloor\; +\; \left\lfloor \frac{20}{2^{3}} \right\rfloor\; +\; ...\; +\; \left\lfloor \frac{20}{2^{5}} \right\rfloor\; \; \; $

Computing this you get there are 18 factors of 2.

Next, find the factors of 3. Using the same method as above except taking powers of 3 instead of powers of 2 you get that there are 8 factors of 3. Each factors of 3 is about 1.5 factor of 2 because $\log_2(3) = 1.5$ so it is like there are 8*1.5 = 12 additional factors of 2.

Next do the same for factors of 5. There are 4 factors of 5, but each factor of 5 is about 2.3 factors of 2 (from $\log_2(5)$) so it is like there are 4*2.5 = 10 extra factors of 2.

In total there are now 18 + 12 + 10 = 40 factors of 2. There will be even more as you can also take 7, 11, 13, 17, and 19 as primes, so it is now clear that 20! is much larger.

$\endgroup$
  • 2
    $\begingroup$ Your 'each factor of 3 is like 1.5 factor of 2' is actually kind of close, but the analysis is wrong. Remember that you're working with exponents - your claim would be that 'each factor of 7 is like 3.5 factors of 2', but in fact two factors of 7 multiply out to 49, whereas 2*3.5 = 7 factors of two (which would be 'equivalent' by your argument) multiply out to 128. $\endgroup$ – Steven Stadnicki Nov 11 '13 at 22:12
  • $\begingroup$ You're right - I should have used log base 2 instead. $\endgroup$ – 1110101001 Nov 12 '13 at 1:43
  • 1
    $\begingroup$ This is what the 'edit' button is for. :-) (But unfortunately, many people won't have logs of 3 and 5 memorized offhand...) $\endgroup$ – Steven Stadnicki Nov 12 '13 at 1:56
  • $\begingroup$ You can just estimate to the nearest integer and it should still work fine. $\endgroup$ – 1110101001 Nov 12 '13 at 6:29
1
$\begingroup$

$20!=1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20$

$20!=2^{1+2+1+3+1+2+1+4+1+2=18}*3^{1+1+2+1+1+2=8}*5^{1+1+1+1=4}*7^{1+1=2}*11^{1}*13^{1}*17^{1}*19^{1} $

$20! \gt 2^{18+8+4+2+1+1}*17^{1}*19^{1}\gt2^{34}*16*16=2^{34}*2^4*2^4>2^{42}>2^{40}$

Hence $20!\gt2^{40}$

I think this is very easy to think...

$\endgroup$
0
$\begingroup$

With Stirling's formula:

$$ 4^n \lt \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \le n! \le e \sqrt{n} \left(\frac{n}{e}\right)^n $$

Both $\le$ are valid for $n\ge1$. Because $e\le 3$ the left inequality is valid a least for all $n \gt 12$.

$\endgroup$
0
$\begingroup$

$$\begin{align}20!&=1\times2\times3\times2^2\times5\times(2\times3)\times7\times2^3\times3^2\times(2\times5)\times11\\&\,\,\,\,\,\,\times(2^2\times3)\times13\times(2\times7)\times(3\times5)\times2^4\times17\times(2\times3^2)\times19\times(2^2\times5)\\&=2^{18}\times3^8\times5^4\times7^2\times11\times13\times17\times19\\&>2^{18}\times2^8\times4^4\times4^2\times2^3\times2^3\times2^4\times2^4=2^{18+8+8+4+3+3+4+4}=2^{52}\\&>2^{40}\end{align}$$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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