2
$\begingroup$

An obvious way to get estimates on $n!$ is to compare $\sum\log k$ to $\int\log t$. If one could get Stirling's formula this way that would strike me as the "right" proof, because it would be clear why it works.

This morning I came much closer to this than I have in the past; in fact fairly straightforward comparisons of sums to integrals show that $$n!\sim c\sqrt n\left(\frac ne\right)^n.$$

Question: I wonder if there's some cheap trick to show that if $n!\sim c\sqrt n(n/e)^n$ then $c=\sqrt{2\pi}$.

$\endgroup$
  • 1
    $\begingroup$ The usual cheap trick is to use Wallis's product formula for $\pi$. $\endgroup$ – Lord Shark the Unknown Aug 1 '18 at 16:22
  • 1
    $\begingroup$ Another relatively straightfoward way would be to calculate the normalization for the Gaussian approximation to the binomial distribution. $\endgroup$ – joriki Aug 1 '18 at 16:32
1
$\begingroup$

You could calculate the normalization for the Gaussian approximation to the binomial distribution.

$\endgroup$
1
$\begingroup$

A Cheap Method

As a function of $k$, $\frac{n^k}{k!}$ reaches its maximum when $k=n-1$ and $k=n$. Furthermore, $$ \begin{align} \log\left(\frac{n^k}{k!}\frac{n!}{n^n}\right) &\stackrel{k\lt n}{=}\log\left[\left(1-\frac0n\right)\left(1-\frac1n\right)\cdots\left(1-\frac{n-k-1}n\right)\right]\\ &\stackrel{k\gt n}{=}\log\left[\frac1{1+\frac1n}\frac1{1+\frac2n}\cdots\frac1{1+\frac{k-n}n}\right] \end{align} $$ Both of these give a second order difference asymptotic to $-\frac1n$.

Therefore, applying Laplace's Method, we get $$ \begin{align} e^n\frac{n!}{n^n} &=\sum_{k=0}^\infty\frac{n^k}{k!}\frac{n!}{n^n}\\ &\sim\int_{-\infty}^\infty e^{-\frac{x^2}{2n}}\,\mathrm{d}x\\[9pt] &=\sqrt{2\pi n} \end{align} $$


A More Detailed Method

For $k\lt n$, $$ \begin{align} &\log\left(\frac{n^k}{k!}\right)-\log\left(\frac{n^n}{n!}\right)\\ &=\log\left(\frac{n-0}{n}\right)+\log\left(\frac{n-1}{n}\right)+\cdots+\log\left(\frac{n-(n-k-1)}{n}\right)\\ &=\sum_{j=0}^{n-k-1}\log\left(1-\frac jn\right)\tag{1a} \end{align} $$ and, bounding a Riemann Sum by integrals, $$ \int_0^{\frac{n-k}n}\log(1-t)\,\mathrm{d}t \le\sum_{j=0}^{n-k-1}\log\left(1-\frac jn\right)\frac1n \le\int_0^{\frac{n-k-1}n}\log(1-t)\,\mathrm{d}t\tag{1b} $$ For $x\in[0,1]$, $-\frac12x^2-\frac12x^3\le\int_0^x\log(1-t)\,\mathrm{d}t\le-\frac12x^2$. Thus, $$ -\frac12\left(\frac{n-k}{\sqrt{n}}\right)^2-\frac1{2\sqrt{n}}\left(\frac{n-k}{\sqrt{n}}\right)^3 \le\sum_{j=0}^{n-k-1}\log\left(1-\frac jn\right) \le-\frac12\left(\frac{n-k-1}{\sqrt{n}}\right)^2\tag{1c} $$ Exponentiating and dividing by $\sqrt{n}$ gives $$ \exp\left(\scriptsize{-\frac12\left(\frac{n-k}{\sqrt{n}}\right)^2-\frac1{2\sqrt{n}}\left(\frac{n-k}{\sqrt{n}}\right)^3}\right)\frac1{\sqrt{n}} \le\frac{n^k}{k!}\frac{n!}{n^n}\frac1{\sqrt{n}} \le\exp\left(\scriptsize{-\frac12\left(\frac{n-k-1}{\sqrt{n}}\right)^2}\right)\frac1{\sqrt{n}}\tag{1d} $$ Summing over $k\in[0,n-1]$ and applying the Squeeze Theorem as $n\to\infty$ yields $$ \lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k=0}^{n-1}\frac{n^k}{k!} =\int_0^\infty e^{-t^2/2}\,\mathrm{d}t\tag{1e} $$


For $k\ge n$, $$ \begin{align} &\log\left(\frac{n^k}{k!}\right)-\log\left(\frac{n^n}{n!}\right)\\ &=\log\left(\frac{n}{n+1}\right)+\log\left(\frac{n}{n+2}\right)+\cdots+\log\left(\frac{n}{n+(k-n)}\right)\\ &=-\sum_{j=1}^{k-n}\log\left(1+\frac jn\right)\tag{2a} \end{align} $$ and, bounding a Riemann Sum by integrals, $$ -\int_0^{\frac{k-n+1}n}\log(1+t)\,\mathrm{d}t \le-\sum_{j=1}^{k-n}\log\left(1+\frac jn\right)\frac1n \le-\int_0^{\frac{k-n}n}\log(1+t)\,\mathrm{d}t\tag{2b} $$ For $x\in[0,1]$, $-\frac12x^2\le-\int_0^x\log(1+t)\,\mathrm{d}t\le-\frac12x^2+\frac16x^3$. Thus, $$ -\frac12\left(\frac{k-n+1}{\sqrt{n}}\right)^2 \le-\sum_{j=1}^{k-n}\log\left(1+\frac jn\right) \le-\frac12\left(\frac{k-n}{\sqrt{n}}\right)^2+\frac1{6\sqrt{n}}\left(\frac{k-n}{\sqrt{n}}\right)^3\tag{2c} $$ Exponentiating and dividing by $\sqrt{n}$ yields $$ \exp\left(\scriptsize{-\frac12\left(\frac{k-n+1}{\sqrt{n}}\right)^2}\right)\frac1{\sqrt{n}} \le\frac{n^k}{k!}\frac{n!}{n^n}\frac1{\sqrt{n}} \le\exp\left(\scriptsize{-\frac12\left(\frac{k-n}{\sqrt{n}}\right)^2+\frac1{6\sqrt{n}}\left(\frac{k-n}{\sqrt{n}}\right)^3}\right)\frac1{\sqrt{n}}\tag{2d} $$ Summing over $k\in[n,2n]$ and applying the Squeeze Theorem as $n\to\infty$ yields $$ \lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k=n}^{2n}\frac{n^k}{k!} =\int_0^\infty e^{-t^2/2}\,\mathrm{d}t\tag{2e} $$


For $t\ge1$, $\log\left(\frac1{1+t}\right)\le-\log(2)$. Using this and $(2b)$, we get, for $k\ge2n$, $$ \begin{align} -\sum_{j=1}^{k-n}\log\left(1+\frac jn\right) &\le-\sum_{j=1}^n\log\left(1+\frac jn\right) -\sum_{j=n+1}^{k-n}\log(2)\\ &\le(1-2\log(2))n-\log(2)(k-2n)\tag{3a} \end{align} $$ Thus, for $k\ge2n$, $$ \frac{n^k}{k!}\le\frac{n^n}{n!}\left(\frac e4\right)^n2^{-(k-2n)}\tag{3b} $$ Therefore, $$ \lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k\gt2n}\frac{n^k}{k!} \le\lim_{n\to\infty}\frac1{\sqrt{n}}\left(\frac e4\right)^n =0\tag{3c} $$


Combining $\text{(1e)}$, $\text{(2e)}$, and $\text{(3c)}$, we get $$ \begin{align} \lim_{n\to\infty}\frac{n!}{n^n}\frac{e^n}{\sqrt{n}} &=\lim_{n\to\infty}\frac{n!}{n^n}\frac1{\sqrt{n}}\sum_{k=0}^\infty\frac{n^k}{k!}\\ &=2\int_0^\infty e^{-x^2/2}\,\mathrm{d}x\\[9pt] &=\sqrt{2\pi}\tag4 \end{align} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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