For what values of $n$ is $10^8 < n! < 10^{12}$?

Question

This question is from the introduction of a handbook on combinatorics. So far, the material covered contains:

• counting problems solved by using trees, Pascal's triangle,...
• definition of $n$ factorial
• definitions of combinations, variations (based on allowing repitition and if order matters).

No formulas, except for the formula for $n$ factorial have been seen.

The question then asks to find all values of $n$ such that $$10^8 < n! < 10^{12}$$ and the given answers states that this holds for $n = 12,13,14$ (only a numerical answer is given, no reasoning).

I tried solving this by taking the logarithm with base 10 from all sides, but this did not really help (seemed to brute force to me).

question: is there some 'nice' way to prove this answer?

Answer 1

For the lower bound, observe that $$10^7=\underbrace{10\cdot 10\cdot ....\cdot 10}_{7\text{ times}}>10\cdot9\cdot8\cdot7\cdot6\cdot4\cdot3=9!\implies 10^8>10\cdot9!=10!$$

Thus $n>10$. Once noticed that $12!$ works (which isn’t very hard) observe the following for the upper bound

if $a\in(10^8, 10^{12})$, then $10^4\cdot a\not\in (10^8, 10^{12})$

In particular $a\cdot 13\cdot 14\cdot 15\cdot 16\not\in (10^8, 10^{12})$ since $a\cdot 13\cdot 14\cdot 15\cdot 16>a\cdot 10^4$.

Hence, since $12!$ satisfies the inequality, $12!\cdot 13\cdot 14\cdot 15\cdot 16=16!$ doesn’t.

Answer 2

There's a nice way (called "Stirling's approximation") to get a narrower estimate, but I think that the goal here was to have you think about things. For instance, you know that $n > 8$, because at $n = 8$, the left hand side is $$ 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 $$ while the middle is $$ 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 $$ Since each factor of the second is smaller than the corresponding factor of the first, you clearly need a larger $n$.

On the other hand, $21!$ has $12$ factors that are at least $10$, namely $10, 11, 12, \ldots, 21$ (as well as a bunch of smaller factors). So $21!$ is definitely bigger than $10^{12}$. At this point, you know that $n$ is between $8$ and $21$, and trying a few numbers in between narrows things down pretty fast.

But along the way, I expect the author hopes that you've learned something about estimating factorials by not-very-subtle methods. (The proof I know of Stirling's formula, for instance, involves integrals.)

Answer 3

By taking logs of both sides, $$8\ln{(10)}\lt\ln{(n!)}\lt12\ln{(10)}$$ Then applying Stirling's approximation we have $$8\ln{(10)}\lt n\ln{(n)}-n+\frac12\ln{(2\pi n)}\lt12\ln{(10)}$$ $$18.4...\lt n\ln{(n)}-n+\frac12\ln{(2\pi n)}\lt27.6...$$ Letting $f(x)=x\ln{(x)}-x+\frac12\ln{(2\pi x)}$ we have that $$f(11)=17.4...$$ $$f(12)=19.9...$$ $$f(13)=22.5...$$ $$f(14)=25.1...$$ $$f(15)=27.8...$$ So the values of $n$ for which this is valid are $12,13$ and $14$.