Approximation for $n!$

Question

One may notice, $$\displaystyle \sum_{k=1}^n \log k=\log n!$$ Applying Integral test for convergence one can obtain, $$\log \left[\dfrac{e^2}{4}\cdot\left(\dfrac{n}{e}\right)^n\right] \le \displaystyle \sum_{k=1}^n \log k\le \log \left[\dfrac{e^2}{2}\cdot\left( \dfrac{n}{e}\right)^n\right]$$ or, say $$\log \left[\dfrac{e^2}{4}\cdot\left(\dfrac{n}{e}\right)^n\right] \le \log n!\le \log \left[\dfrac{e^2}{2}\cdot\left( \dfrac{n}{e}\right)^n\right]$$ Now playing with exponents gives us, $$\dfrac{e^2}{4}\cdot\left(\dfrac{n}{e}\right)^n \le n!\le \dfrac{e^2}{2}\cdot\left( \dfrac{n}{e}\right)^n$$ The higher bound $\dfrac{e^2}{2}\cdot\left( \dfrac{n}{e}\right)^n$ gives a good approximation for $n!$ but it's not so good compared to Stirling's approximation. Any explanation for this or, idea to improve this any further?

Answer 1

Edit: This started as random estimates on $n!$. It turns out that one can actually prove Stirling's formula this way, if one believes Wallis's formula for $\pi$.

In fact your upper bound is wrong. Stirling says $$\frac{n!}{(n/e)^n}\sim\sqrt{2\pi n},$$hence $n!$ is not bounded above by $c(n/e)^n$.

Possibly you did the integral wrong, or more likely you compared the sum to the wrong integral. You can get valid bounds by this method. Noting that $\log(n!)=\sum_{k=2}^n\log(k)$ it follows that $$\int_1^n\log(t)\,dt\le\log(n!)\le\int_2^{n+1}\log(t)\,dt;$$now note that $\int\log(t)\,dt=t\log(t)-t$ and see what happens... When I do the calculus I get $$e\left(\frac ne\right)^n\le n!\le\frac e4\frac{(n+1)^{n+1}}{e^n}.$$ Note I didn't do the calculus very carefully.

This is very crude; the upper and lower bounds differ by roughly a factor of $cn$. (In fact Stirling's formula shows that the truth is just a constant times the geometric mean of the upper and lower bounds, a satisfying sanity check.) The reason it's so bad is we're using just $\int_{k-1}^k\log t\le\log k\le\int_k^{k+1}\log t$, which is pretty rough.

You could get a better estimate, with upper and lower bounds differing by a constant, by comparing $\log k$ to $\int_{k-1/2}^{k+1/2}\log t$. Except now the comparison is not so trivial. For example, $$\begin{align}\log k-\int_{k-1/2}^{k+1/2}\log t&=\int_0^{1/2} 2\log k-(\log(k+t)+\log(k-t)) \\&=\int_0^{1/2}\log\left(1+\frac{t^2}{k^2-t^2}\right) \\&\le\int_0^{1/2}\frac{t^2}{k^2-t^2} \\&\le\frac1{k^2-1/4}\int_0^{1/2}t^2 \\&=\frac1{24}\frac1{(k-1)^2},\end{align}$$so that $$0\le\log(n!)-\int_{3/2}^{n+1/2}\log t\le\frac{\pi^2}{144}.$$I'm not going to bother working out that last integral, since this doesn't quite give Stirling's formula anyway. But it does give estimates within a constant of Stirling's formula...

No wait! Actually this does give Stirling's formula, except with an unknown constant. The above shows that $\sum|\log k-\int_{k-1/2}^{k+1/2}\log t|<\infty$, and hence there exists a finite $c$ so that $$\log(n!)-\int_{3/2}^{n+1/2}\log t\to c.$$So (letting the value of $c$ vary from line to line), $$\log(n!)-((n+1/2)\log(n+1/2)-n)\to c.$$ Now $$\frac{(n+1/2)^{n+1/2}}{n^n}\sim\sqrt n\left(\frac{n+1/2}{n}\right)^n\sim c\sqrt n,$$ so we get $$n!\sim c\sqrt n\left(\frac ne\right)^n.$$

Bonus I asked elsewhere whether there was a trick to find $c$ here. Someone suggested Wallis's formula. Sure enough: Wallis's formula says that $$\frac\pi 2=\lim_{n\to\infty}\frac1{2n+1}\frac{2^{4n}(n!)^4}{((2n)!)^2}.$$If you insert $n!\sim c\sqrt n(n/e)^n$ it follows that $c=\sqrt{2\pi}$, and we have Stirling's formula.