4
$\begingroup$

I need a proof of stirling's formula which uses the riemann's sum and trapezoid approximation to come up with $ \frac {n!}{(n/e)^n \sqrt n}$ $ \rightarrow C$ where $C$ is derived from Wallis product. I tried searching the internet but was not able to come up with anything.

$\endgroup$
  • 1
    $\begingroup$ Note that $$\ln(n!)=\sum_{k=1}^n \ln(k)$$ for which $$\int_1^n \ln(x)dx < \sum_{k=1}^n \ln(k) < \int_1^{n+1} \ln(x) dx$$ $\endgroup$ – JasonM Jul 22 '16 at 22:37
  • 1
    $\begingroup$ Also en.wikipedia.org/wiki/Wallis_product has a section on its relation to stirling's approximation $\endgroup$ – JasonM Jul 22 '16 at 22:45
  • $\begingroup$ It's a pretty mechanical derivation of stirlings from Wallis product, they are really the same thing $\endgroup$ – qbert Jul 30 '16 at 17:55
4
$\begingroup$

First note that we can write

$$\begin{align} \log(n!)&=\sum_{k=1}^n \log(k)\\\\ &=n\log(n)+\sum_{k=1}^n\log(k/n)\\\\ &=n\left(\log(n)+\frac1n\sum_{k=1}^n\log(k/n)\right) \\\\ &=n\left(\log(n)+\int_0^1 \log(x)\,dx\right)-n\left(\int_0^1 \log(x)\,dx-\frac1n \sum_{k=1}^n \log(k/n)\right)\\\\ &=\log\left(\left(\frac ne\right)^n\right)-n\left(\int_0^1 \log(x)\,dx-\frac1n \sum_{k=1}^n \log(k/n)\right)\tag 1 \end{align}$$

Next, we write the integral on the right-hand side of $(1)$ as

$$\begin{align} \int_{0}^1 \log(x)\,dx&=\int_0^{1/n}\log(x)\,dx+\sum_{k=1}^{n-1}\int_{k/n}^{(k+1)/n} \log(x)\,dx \\\\ &=-\frac1n\left(\log(n)+1\right)+\sum_{k=1}^{n-1}\int_{k/n}^{(k+1)/n} \log(x)\,dx \tag2 \end{align}$$

Applying the Trapezoidal Rule to the integral in $(2)$ reveals

$$\int_{k/n}^{(k+1)/n} \log(x)\,dx =\frac1{2n} \left(\log\left(\frac{k+1}{n}\right)+\log\left(\frac{k}{n}\right)\right)+\frac{1}{12n^3}\frac{1}{\xi^2} \tag3$$

where $k/n<\xi<(k+1)/n$.

Inserting $(3)$ into $(2)$ yields

$$\int_0^1 \log(x)\,dx =-\frac1{2n}\log(n)+\frac1n\sum_{k=1}^n\log(k/n)+O\left(\frac{1}{n}\right)\tag 4$$

Substituting $(4)$ into $(1)$ we find that

$$\log(n!)=\log\left(\left(\frac ne\right)^n\right)+\frac12\log(n)+O\left(1\right)$$

whereupon rearranging terms gives

$$\log\left(\frac{n!}{\sqrt{n}\left(\frac{n}{e}\right)^n}\right)=O\left(1\right) \tag 5$$

Finally, exponentiation of $(5)$ yields

$$\begin{align} \frac{n!}{\sqrt{n}\left(\frac{n}{e}\right)^n}&=e^{O\left(1\right)}\\\\ &=O(1) \end{align}$$

whereupon taking the limit gives

$$\lim_{n\to \infty}\frac{n!}{\sqrt{n}\left(\frac{n}{e}\right)^n}=C$$

for some constant $C$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Great answer, was fun to read through and I'll definitely reference this in the future. More importantly, it was an easy read, even for someone like myself who has self studied much of my mathematical knowledge (unfortunately, high schools today are getting more and more rigid, just focusing on standardized testing... sigh it leaves people like myself who could easily take a real analysis course stuck in a basic Pre-Calculus course) Ill have to verify a few of the steps for myself (applying the trapezoidal rule and everything after it is pretty condensed in the proof)... $\endgroup$ – Brevan Ellefsen Jul 30 '16 at 18:04
  • $\begingroup$ ... and then I feel I could show this to some of my more mathematically inclined peers. Again, thank you for taking the time to write such a wonderful answer! $\endgroup$ – Brevan Ellefsen Jul 30 '16 at 18:04
  • $\begingroup$ @BrevanEllefsen Wow! Brevan, thank you for this note. It made my weekend. I just hope that there were no fatal flaws in my development. -Mark $\endgroup$ – Mark Viola Jul 30 '16 at 18:05
  • $\begingroup$ @BrevanEllefsen I definitely feel you about that school system. $\endgroup$ – Simply Beautiful Art Jan 3 '17 at 1:12
3
$\begingroup$

I wrote the following derivation for this answer, but it seems relevant to this question. In $(1)$, we write an integral over a unit interval as the value at the middle of the interval plus an error term. This is a Riemann sum with error term.


First $$ \begin{align} \int_{k-1/2}^{k+1/2}\log(x)\,\mathrm{d}x &=\int_k^{k+1/2}\log(x)\,\mathrm{d}x+\int_{k-1/2}^k\log(x)\,\mathrm{d}x\\ &=\int_0^{1/2}\log(k+t)\,\mathrm{d}x+\int_0^{1/2}\log(k-t)\,\mathrm{d}t\\ &=\int_0^{1/2}\log\left(k^2-t^2\right)\,\mathrm{d}t\\ &=\log(k)+\int_0^{1/2}\log\left(1-\frac{t^2}{k^2}\right)\,\mathrm{d}t\tag{1} \end{align} $$ Euler's Product Formula for $\sin(\pi t)$ easily leads to $$ \sum_{k=1}^\infty\log\left(1-\frac{t^2}{k^2}\right)=\log\left(\frac{\sin(\pi t)}{\pi t}\right)\tag{2} $$ Using symmetry and a double angle formula, we get $$ \begin{align} \int_0^{1/2}\log(\sin(\pi t))\,\mathrm{d}t &=\frac12\int_0^1\log(\sin(\pi t))\,\mathrm{d}t\\ &=\int_0^{1/2}\log(\sin(2\pi t))\,\mathrm{d}t\\ &=\frac12\log(2)+\int_0^{1/2}\log(\sin(\pi t))\,\mathrm{d}t+\int_0^{1/2}\log(\cos(\pi t))\,\mathrm{d}t\\ &=\frac12\log(2)+2\int_0^{1/2}\log(\sin(\pi t))\,\mathrm{d}t\\[3pt] &=-\frac12\log(2)\tag{3} \end{align} $$ Using $(1)$, $(2)$, $(3)$, and $\log\left(n+\tfrac12\right)=\log(n)+\frac1{2n}+O\!\left(\frac1{n^2}\right)$, we get $$ \begin{align} \log(n!) &=\sum_{k=1}^n\log(k)\\ &=\int_{1/2}^{n+1/2}\log(x)\,\mathrm{d}x-\sum_{k=1}^n\int_0^{1/2}\log\left(1-\frac{t^2}{k^2}\right)\,\mathrm{d}t\\ &=\int_{1/2}^{n+1/2}\log(x)\,\mathrm{d}x-\int_0^{1/2}\log\left(\frac{\sin(\pi t)}{\pi t}\right)\,\mathrm{d}t+\sum_{k=n+1}^\infty \int_0^{1/2}\log\left(1-\frac{t^2}{k^2}\right)\,\mathrm{d}t\\ &=\int_0^{n+1/2}\log(x)\,\mathrm{d}x+\tfrac12\log(\pi)-\int_0^{1/2}\log(\sin(\pi t))\,\mathrm{d}t+\sum_{k=n+1}^\infty O\!\left(\frac1{k^2}\right)\\[6pt] &=\left(n+\tfrac12\right)\log\left(n+\tfrac12\right)-\left(n+\tfrac12\right)+\tfrac12\log(\pi)+\tfrac12\log(2)+O\!\left(\tfrac1n\right)\\[12pt] &=\left(n+\tfrac12\right)\log(n)-n+\tfrac12\log(2\pi)+O\!\left(\tfrac1n\right)\\[12pt] &=n\log(n)-n+\tfrac12\log(2\pi n)+O\!\left(\tfrac1n\right)\tag{4} \end{align} $$ Equation $(4)$ is equivalent to $$ \bbox[5px,border:2px solid #C0A000]{n!=\sqrt{2\pi n}\,\frac{n^n}{e^n}\left(1+O\!\left(\frac1n\right)\right)}\tag{5} $$


A Useful Representation

We can collect terms from the derivation of equation $(4)$ to get $$ \begin{align} \log(n!) &=\int_0^{n+1/2}\log(x)\,\mathrm{d}x+\tfrac12\log(2\pi)+\sum_{k=n+1}^\infty \int_0^{1/2}\log\left(1-\frac{t^2}{k^2}\right)\,\mathrm{d}t\\ &=\int_0^{n+1/2}\log(x)\,\mathrm{d}x+\tfrac12\log(2\pi)+\sum_{k=1}^\infty \int_0^{1/2}\log\left(1-\frac{t^2}{(n+k)^2}\right)\,\mathrm{d}t\tag{6} \end{align} $$ which is analytic in $n$ and, as shown in this answer, convex on the positive reals.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And, of course, you can use $\int \log x dx = x\log x - x$. Usually the hard part is getting the constant. $\endgroup$ – marty cohen Aug 12 '17 at 16:39
  • $\begingroup$ @martycohen: yes, that is the reason I wrote this answer: it gives the constant in a fairly painless manner. $\endgroup$ – robjohn Aug 12 '17 at 16:49

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.