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.
On
You can simply compute both numbers and compare them: $$ 20! = 2432902008176640000 \\ 2^{40} = 1099511627776 $$
So you can easily see that $2^{40} < 20!$
On
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}$.
On
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.
On
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.
On
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.
On
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}$.
On
$$\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
On
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.
On
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.
On
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.
On
$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}$
On
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
On
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$.
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.