Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
You can simply compute both numbers and compare them: $$ 20! = 2432902008176640000 \\ 2^{40} = 1099511627776 $$
So you can easily see that $2^{40} < 20!$
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}$.
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}$.
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.
$$\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
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.
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.
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.
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
$$\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}$$
$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}$
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.
$\log _{10}\left( {2^{40} } \right)=40 \log _{10}\left( {2} \right)= 12,04$ so the numbers of digits of $2^{40}$=13
$\log _{10}\left( {20! } \right)=\sum _{1}^{20} \log_{10} \left({x})\right)=18,38$ so the numbers of digits of 20! Is $19$
So $ 20!>2^{40} $
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$.
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.
$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...
