Stirling’s approximation of n!

n!=1\times 2\times 3\times\dots\times n
Since working with sums is easier than working with products, we take the logarithm base e of both sides,

    \[\ln n!=\ln 1+ \ln 2+ \ln 3+\dots+\ln n=\sum\limits_{k=1}^n \ln k\]

and try to find expressions for the lower and upper bounds, i.e.

    \[\text{? }<\ln 1+\ln 2+ \ln 3+ \ln 4+\dots+\ln n<\text{ ?}\]

getting a lower bound

integrating ln x

\int \ln x \;\text{d}x can be integrated by parts, with U=\ln x and the rest as \text{d}V:

    \begin{align*} &&U&=\ln x, &&&\text{d}V&=\text{d} x &&&\\ &&\text{d}U&=\fr{x}\;\text{d}x,&&& V&=x&&& \end{align*}

    \begin{align*} \int U \;\text{d}V&=UV-\int V \;\text{d}U \\ \text{i.e. }\qquad\int \ln x \;\text{d}x&=x \ln x - \int x \fr{x} \;\text{d}x\\ &=x \ln x -x +C \end{align*}

Checking this by differentiating:

    \[\frac{\text{d}(x\ln x-x+C)}{\text{d}x}=x\fr{x}+\ln x-1=\ln x\]

Plug in x=1 to find C:

    \[\int\limits_1^1 \ln x \;\text{d}x=0=x\ln x-x+C=1\times0-1+C \qquad\to\qquad C=1\]

    \[\boxed{\int\limits_1^n \ln x \;\text{d}x=n\ln x-n+1}\]

trapezoid rule approximation
ln x trap
To approximate the area under the curve, add the area of the trapezoids. Since the curve is concave downwards, this will underestimate the area.
Each trapezoid has an area of the average of the sides, times the width (1). i.e. the area of the trapezoid between x=2 and 3 is \displaystyle\frac{\ln 2+\ln 3}{2}. As all terms except the first and last occur twice in the sum, it comes to:

    \[\fr{2}\ln 1+\ln 2+\ln 3+\dots+\ln (n-1)+\fr{2}\ln n< n\ln n-n+1\]

Since \ln 1=0, add \fr{2}\ln n to both sides to get:

    \[(\ln 1+)\ln 2+\ln 3+\dots+\ln (n-1)+\ln n< n\ln n-n+1+\fr{2}\ln n\]


    \begin{align*} \ln n!&<n\ln n-n+1+\fr{2}\ln n \\ &=\ln n^n-n+1+\ln \sqrt{n} \end{align*}

Raise both sides to the power of e (anti-log):

    \[n!<n^n e^{-n} e \sqrt{n}\]

getting an upper bound
midp log


Richard Hamming – Methods of Mathematics, ch.15

Leave a Reply

Your email address will not be published. Required fields are marked *