Exercise 8.20

Question

Exercise 20: 
    The following simple computation yields a good approximation to Stirling's formula. For $m=1,2,3,\ldots,$ define $$f(x)=(m+1-x)\log m+(x-m)\log(m+1)$$ if $m\le x\le m+1$, and define
    $$g(x)=\frac{x}{m}-1+\log m$$ if $m-1/2\le x<m+1/2$. Draw the graphs of $f$ and $g$. Note that $f(x)\le\log x\le g(x)$ if $x\ge 1$ and that $$\int_1^n f(x)\,dx=\log(n!)-\frac{\log n}{2}>
    -\frac{1}{8}+\int_1^n g(x)\,dx.$$ Integrate $\log x$ over $[1,n]$. Conclude that $$\frac{7}{8}<\log(n!)-\bigg(n+\frac{1}{2}\bigg)\log n+n<1$$ for $n=2,3,4,\ldots.$ Thus $$e^{7/8}<
    \frac{n!}{(n/e)^n\sqrt{n}}<e.$$

analambanomenos · Accepted Answer

\def\ints{\mathbb{Z}}

The second derivative of $\log x$ is $-x^{-2}$, which is negative for $x>0$, so $\log x$ is a ``concave'' function (i.e., $-\log x$ is convex). The function $f(x)$ is a continuous,
    piecewise-linear function whose values at the endpoints of the linear segments, $f(m)$ for $m=1,2,\ldots,$ equal $\log m$, hence $f(x)\le\log x$ by the concavity of $\log x$. Also, $g(x)$ is a
    continuous, piecewise-linear function which is equal to $\log m$ at $m=1,2,\ldots,$ and the slope of $g(x)$ is equal to the derivative of $\log x$ at those points. That is, the linear segments
    of $g(x)$ are tangent to $\log x$ at those points, and so $\log x\le g(x)$, also by the concavity of the $\log x$.

\begin{align*}
        \int_1^nf(x)\,dx &= \sum_{m=1}^{n-1}\int_m^{m+1}(m+1-x)\log m+(x-m)\log(m+1)\,dx \
        &= \sum_{m=1}^{n-1}\big(-	extstyle\frac{1}{2}(m+1-x)^2\log m+\frac{1}{2}(x-m)^2\log(m+1)\big)\big|_{x=m}^{x=m+1} \
        &= 	extstyle\frac{1}{2}\log 1+\displaystyle\sum_{m=1}^{n-1}(\log m)+	extstyle\frac{1}{2}\log n \
        &= \log n!-	extstyle\frac{1}{2}\log n \
        \int_1^ng(x)\,dx &= \int_1^{\frac{3}{2}}(x-1+\log 2)\,dx+\sum_{m=2}^{n-1}\int_{m-\frac{1}{2}}^{m+\frac{1}{2}}\bigg(\frac{x}{m}-1+\log m\bigg)\,dx+\int_{n-\frac{1}{2}}^n
           \bigg(\frac{x}{n}-1+\log n\bigg)\,dx \
        &= 	extstyle\frac{1}{2}(x-1)^2\big|_{x=1}^{x=\frac{3}{2}}+\displaystyle\sum_{m=2}^{n-1}	extstyle\big(\frac{1}{2m}x^2-x+x\log m\big)\big|_{x=m-\frac{1}{2}}^{x=m+\frac{1}{2}}+
           \big(\frac{1}{2n}x^2-x+x\log n\big)\big|_{x=n-\frac{1}{2}}^{x=n} \
        &= 	extstyle\frac{1}{8}+\displaystyle\sum_{m=2}^{n-1}\big(1-1+\log m)+\big(	extstyle\frac{1}{2}-\frac{1}{8n}-\frac{1}{2}+\frac{1}{2}\log n\big) \
        &= \log n!-	extstyle\frac{1}{2}\log n +\frac{1}{8}\big(1-\frac{1}{n}\big) \
        &< \int_1^nf(x)\,dx+	extstyle\frac{1}{8}
    \end{align*}
    Integrating by parts, we have $\int_1^n\log x\,dx=n\log n-1\log1-\int_1^n1\,dx=n\log n-n+1$. Hence
    \begin{gather*}
        -\int_1^ng(x)\,dx<-\int_1^n\log x\,dx<-\int_1^nf(x)\,dx \
        -\log n!+	extstyle\frac{1}{2}\log n-\frac{1}{8}<-n\log n+n-1<-\log n!+\frac{1}{2}\log n
    \end{gather*}
    Adding $1+\log n!-\frac{1}{2}\log n$ to all sides, we get $$	extstyle\frac{7}{8}<\log n!-\big(n+\frac{1}{2}\big)\log n+n<1.$$
    And applying $\exp$ to all sides, we get
    \begin{gather*}
        e^{7/8}<\frac{\exp\big(\log n!\big)\exp(n)}{\exp\big(\log(n^{n+1/2})\big)}<e \
        e^{7/8}<\frac{n!e^n}{n^n\sqrt{n}}<e \
        e^{7/8}<\frac{n!}{(n/e)^n\sqrt{n}}<e
    \end{gather*}

Exercise 8.20

Answers

Comments

Exercise 8.20

Answers

Comments

Add answer