4

In the paper Decomposable Searching Problems I. Static-to-Dynamic Transformations by Bentley and Saxe, the authors state without proof that

$$\sqrt[n]{n!} \sim {\frac{n}{e}}\text.$$

I have a line of reasoning below that I think correctly proves this, but I'm a bit shaky about whether I can apply tilde approximations this way. Is this reasoning correct?

Using Stirling's approximation, we know that

$$n! \sim \left(\frac{n}{e}\right)^n \sqrt{2\pi n}\text.$$

Taking $n$th roots then gives

$$\sqrt[n]{n!} \sim \left( \frac{n}{e} \right) \sqrt[2n]{2 \pi n} \sim \frac{n}{e}\text.$$

The step I'm uncomfortable about is whether I can take $n$th roots of both sides of the tilde expression. This feels like it "ought" to work, but I've been surprised by tilde expressions in the past and wouldn't want to bet the farm on it. :-)

templatetypedef
  • 10,206
  • 5
    A handy trick for not being surprised by these tilde expressions again is to translate them into what they actually mean in terms of limits and ratios. – Arthur Jun 06 '22 at 23:55
  • Shouldn't it be $\sqrt[2n]{2 \pi n}$? – ewokx Jun 06 '22 at 23:57
  • @ewong Yes, thank you! – templatetypedef Jun 06 '22 at 23:57
  • @Arthur That's what I usually do. :-) In this particular case, I'm not sure how taking the $n$th root factors in, since this feels like something where l'Hopital's rule would kick in in a way that would make the expression a lot more complicated. – templatetypedef Jun 07 '22 at 00:01
  • You can work with $$ n! = \left( {\frac{n}{e}} \right)^n \sqrt {2\pi n} \left( {1 + \mathcal{O}!\left( {\frac{1}{n}} \right)} \right). $$ Of course there are more elementary ways of getting the asymptotics, which do not use Stirling's formula. – Gary Jun 07 '22 at 00:01
  • It should indeed be $2n$ but $\sqrt[n]{2\pi n} \sim 1$ for large $n$ as well. – Mike Jun 07 '22 at 00:01
  • Note the $\sqrt{2\pi}$ is the difficult part in the Stirling formula but you can prove that $\dfrac{n!e^n}{\sqrt{n}n^n}\to c>0$ more easily, have a look here https://math.stackexchange.com/a/3660494/399263 – zwim Jun 07 '22 at 01:44

4 Answers4

4

Suppose that $a_n\sim b_n$ as $n\to +\infty$. This means, by definition, that, in particular, $$ \frac{1}{2}<\frac{a_n}{b_n}<\frac{3}{2} $$ for all sufficiently large $n$. Taking $n$th roots and using the squeeze theorem shows that $\sqrt[n]\frac{a_n}{b_n}=\frac{\sqrt[n]{a_n}}{\sqrt[n]{b_n}} \to 1$, i.e., $\sqrt[n]{a_n} \sim \sqrt[n]{b_n}$ as $n\to +\infty$.

You can apply this observation to $a_n=n!$ and $b_n=\left( {\frac{n}{\mathrm{e}}} \right)^n \sqrt {2\pi n}$.

Gary
  • 31,845
4

You may just use the following

Lemma if $\{a_n\}_{n\geq 1}$ is a sequence of positive numbers such that $\lim_{n\to +\infty}\frac{a_{n+1}}{a_n}=L$, then $\lim_{n\to +\infty}\sqrt[n]{a_n}=L$.

Apply the Lemma to $a_n = \frac{n!}{n^n}$ in order to get

$$ \lim_{n\to +\infty}\sqrt[n]{\frac{n!}{n^n}} = \lim_{n\to +\infty}\frac{1}{\left(1+\frac{1}{n}\right)^n}=\frac{1}{e}.$$

Jack D'Aurizio
  • 353,855
3

$$\begin{align*}\lim_{n\to\infty}\big(\frac{\ln(n!)}{n}-\ln(n)\big)&=\lim_{n\to\infty}\frac1n\big(\ln(\frac1n)+\ln(\frac2n)+\dots+\ln(\frac nn)\big)\\ &=\int_0^1\ln(x)dx\\ &=[x\ln x-x]_0^1=-1.\end{align*}$$

Kenta S
  • 16,151
  • 15
  • 26
  • 53
  • While this derivation explains why the result holds, I’m not sure if it directly addresses my question of whether the step I’m proposing is correct. Is there a connection between what you’ve written here and the step I’ve flagged? – templatetypedef Jun 07 '22 at 01:08
  • 1
    Not really. However, I would like to comment that Stirling's approximation is a refining of this asymptotic, so it is anachronistic to use Stirling's approximation to "derive" $\sqrt[n]{n!}\sim n/e$. – Kenta S Jun 07 '22 at 01:35
0

$$a_n=\sqrt[n]{n!} \qquad \implies \qquad \log(a_n)=\frac 1 n \log(n!)$$ Now, using Stirling approximation $$ \log(a_n)=\log (n)-1+\frac{\log (2 \pi n)}{2 n}+\frac{1}{12 n^2}-\frac{1}{360 n^4}+O\left(\frac{1}{n^6}\right)$$ Continuing with Taylor series $$a_n=e^{\log(a_n)}=\frac{n}{e}\,\exp\Bigg[\frac{\log (2 \pi n)}{2 n}+\frac{1}{12 n^2}-\frac{1}{360 n^4}+O\left(\frac{1}{n^6}\right) \Bigg]$$

Use it $\large (!!)$ for $n=4$ . The above truncated series gives $$\frac{4\ 2^{3/8} \sqrt[8]{\pi }}{e^{91681/92160}}=\color{red}{2.213363}43\quad \text{while} \quad \sqrt[4] {4!}=\color{red}{2.21336384}$$

Claude Leibovici
  • 260,315