Problem source

A definite integral can be evaluated approximately by means of the Trapezium rule:
	\[
	\int_{x_{0}}^{x_{N}}\mathrm{f}(x)\,\mathrm{d}x\approx\tfrac{1}{2}h\left\{ \mathrm{f}\left(x_{0}\right)+2\mathrm{f}\left(x_{1}\right)+\ldots+2\mathrm{f}\left(x_{N-1}\right)+\mathrm{f}\left(x_{N}\right)\right\} ,
	\]
	where the interval length $h$ is given by $Nh=x_{N}-x_{0}$, and $x_{r}=x_{0}+rh$. Justify briefly this approximation. 
	Use the Trapezium rule with intervals of unit length to evaluate approximately the integral 
	\[
	\int_{1}^{n}\ln x\,\mathrm{d}x,
	\]
	where $n(>2)$ is an integer. Deduce that $n!\approx\mathrm{g}(n)$, where 
	\[
	\mathrm{g}(n)=n^{n+\frac{1}{2}}\mathrm{e}^{1-n},
	\]
	and show by means of a sketch, or otherwise, that 
	\[
	n!<\mathrm{g}(n).
	\]
	By using the Trapezium rule on the above integral with intervals of width $k^{-1}$, where $k$ is a positive integer, show that 
	\[
	\left(kn\right)!\approx k!n^{kn+\frac{1}{2}}\left(\frac{\mathrm{e}}{k}\right)^{k\left(1-n\right)}.
	\]
	Determine whether this approximation or $\mathrm{g}(kn)$ is closer to $\left(kn\right)!$.

Solution source

\begin{center}
\begin{tikzpicture}
  % Define function
  \def\f(#1){0.7*sin(#1*90+30)+0.1*sin(280*#1) + 1.5}
  
  % Set up the coordinate system
  \draw[thick, ->] (-0.5,0) -- (5.5,0) node[right] {$x$};
  \draw[thick, ->] (0,-0.5) -- (0,3.5) node[above] {$f(x)$};
  
  % Add tick marks and labels
  \foreach \x in {0,1,2,3,4,5} {
    \draw (\x,0.1) -- (\x,-0.1) node[below] {$x_{\x}$};
  }
  
  % Calculate function values
  \pgfmathsetmacro{\fa}{\f(0)}
  \pgfmathsetmacro{\fb}{\f(1)}
  \pgfmathsetmacro{\fc}{\f(2)}
  \pgfmathsetmacro{\fd}{\f(3)}
  \pgfmathsetmacro{\fe}{\f(4)}
  \pgfmathsetmacro{\ff}{\f(5)}
  
  % Plot the function curve
  \draw[thick, blue, samples=100, smooth, domain=0:5] plot (\x, {\f(\x)});
  \node[blue, right] at (5, \ff) {$f(x)$};
  
  % Draw the trapezoids
  \fill[red!30, opacity=0.6] (0,0) -- (0,\fa) -- (1,\fb) -- (1,0) -- cycle;
  \fill[red!30, opacity=0.6] (1,0) -- (1,\fb) -- (2,\fc) -- (2,0) -- cycle;
  \fill[red!30, opacity=0.6] (2,0) -- (2,\fc) -- (3,\fd) -- (3,0) -- cycle;
  \fill[red!30, opacity=0.6] (3,0) -- (3,\fd) -- (4,\fe) -- (4,0) -- cycle;
  \fill[red!30, opacity=0.6] (4,0) -- (4,\fe) -- (5,\ff) -- (5,0) -- cycle;
  
  % Add vertical lines and function value labels
  \draw[dashed] (0,\fa) -- (0,0);
  \node[left] at (0,\fa) {$f(x_0)$};
  
  \draw[dashed] (1,\fb) -- (1,0);
  \node[above] at (1,\fb) {$f(x_1)$};
  
  \draw[dashed] (2,\fc) -- (2,0);
  \node[above] at (2,\fc) {$f(x_2)$};
  
  \draw[dashed] (3,\fd) -- (3,0);
  \node[above] at (3,\fd) {$f(x_3)$};
  
  \draw[dashed] (4,\fe) -- (4,0);
  \node[above] at (4,\fe) {$f(x_4)$};
  
  \draw[dashed] (5,\ff) -- (5,0);
  \node[above] at (5,\ff) {$f(x_5)$};
  
  % Add trapezoid labels
  \node at (0.5,0.4) {$T_1$};
  \node at (1.5,0.4) {$T_2$};
  \node at (2.5,0.4) {$T_3$};
  \node at (3.5,0.4) {$T_4$};
  \node at (4.5,0.4) {$T_5$};
 
\end{tikzpicture}
\end{center}

We can approximate the integral by $N$ trapeziums, each with height $x_{i+1}-x_{i} = \frac{x_N-x_0}{N} = \frac{h}{N}$. The will have area $\frac{(f(x_i)+f(x_{i+1}))h}{2}$ and summing all these areas we will get:

\[\frac12 h \l f(x_0) + f(x_1) + f(x_1)+f(x_2) + \cdots + f(x_{N-1})+f(x_N) \r = \frac12 h \l f(x_0) +2 f(x_1) + + \cdots +2f(x_{N-1})+f(x_N) \r\]

But this is approximately the integral $\displaystyle \int_{x_0}^{x_N} f(x) \d x$

\begin{align*}
&& \int_1^n \ln x \d x &= [x \ln x]_1^n - \int_1^n x \cdot \frac{1}{x} \d x \\
&&&= n \ln n - n+1 \\
&&&\approx \frac12  \l \ln 1 + 2\sum_{k=2}^{n-1}  \ln k + \ln n \r \\
&&&= \ln (n!) - \frac12 \ln n \\
\Rightarrow && \ln (n!) &\approx n \ln n + \frac12 \ln n - n + 1 \\
\Rightarrow && n! &\approx \exp(n \ln n + \frac12 \ln n - n + 1) \\
&&&=n^{n+\frac12}e^{1-n}
\end{align*}

Since $\ln x$ is a concave function, we should expect all the trapeziums to all lie under the curve, therefore this is always an underestimate for the integral, ie $n! < g(n)$

\begin{tikzpicture}
  % Define function
  \def\f(#1){ln(1+(#1)/0.25)}
  
  % Set up the coordinate system
  \draw[thick, ->] (-0.5,0) -- (5.5,0) node[right] {$x$};
  \draw[thick, ->] (0,-0.5) -- (0,3.5) node[above] {$f(x)$};
  
  % Add tick marks and labels
  \foreach \x in {0,1,2,3,4,5} {
    \draw (\x,0.1) -- (\x,-0.1) node[below] {$x_{\x}$};
  }
  
  % Calculate function values
  \pgfmathsetmacro{\fa}{\f(0)}
  \pgfmathsetmacro{\fb}{\f(1)}
  \pgfmathsetmacro{\fc}{\f(2)}
  \pgfmathsetmacro{\fd}{\f(3)}
  \pgfmathsetmacro{\fe}{\f(4)}
  \pgfmathsetmacro{\ff}{\f(5)}
  
  % Plot the function curve
  \draw[thick, blue, samples=100, smooth, domain=0:5] plot (\x, {\f(\x)});
  \node[blue, right] at (5, \ff) {$f(x)$};
  
  % Draw the trapezoids
  \fill[red!30, opacity=0.6] (0,0) -- (0,\fa) -- (1,\fb) -- (1,0) -- cycle;
  \fill[red!30, opacity=0.6] (1,0) -- (1,\fb) -- (2,\fc) -- (2,0) -- cycle;
  \fill[red!30, opacity=0.6] (2,0) -- (2,\fc) -- (3,\fd) -- (3,0) -- cycle;
  \fill[red!30, opacity=0.6] (3,0) -- (3,\fd) -- (4,\fe) -- (4,0) -- cycle;
  \fill[red!30, opacity=0.6] (4,0) -- (4,\fe) -- (5,\ff) -- (5,0) -- cycle;
  
  % Add vertical lines and function value labels
  \draw[dashed] (0,\fa) -- (0,0);
  \node[left] at (0,\fa) {$f(x_0)$};
  
  \draw[dashed] (1,\fb) -- (1,0);
  \node[above] at (1,\fb) {$f(x_1)$};
  
  \draw[dashed] (2,\fc) -- (2,0);
  \node[above] at (2,\fc) {$f(x_2)$};
  
  \draw[dashed] (3,\fd) -- (3,0);
  \node[above] at (3,\fd) {$f(x_3)$};
  
  \draw[dashed] (4,\fe) -- (4,0);
  \node[above] at (4,\fe) {$f(x_4)$};
  
  \draw[dashed] (5,\ff) -- (5,0);
  \node[above] at (5,\ff) {$f(x_5)$};
  
  % Add trapezoid labels
  \node at (0.5,0.4) {$T_1$};
  \node at (1.5,0.4) {$T_2$};
  \node at (2.5,0.4) {$T_3$};
  \node at (3.5,0.4) {$T_4$};
  \node at (4.5,0.4) {$T_5$};
 
\end{tikzpicture}


\begin{align*}
&& \int_1^n \ln x \d x &= n \ln n - n+1 \\
&&&\approx \frac12 k^{-1} \l \ln 1 + 2\sum_{r=1}^{k(n-1)-1}  \ln \l 1+\frac{r}{k} \r + \ln n \r \\
&&&=\frac{1}{2k} \l 2\sum_{r=1}^{k(n-1)-1} \l \ln(k+r) - \ln k)\r + \ln n\r \\
&&&=\frac1{k} \l \ln ((k+k(n-1)-1)!) - \ln(k!) - (k(n-1)-1) \ln k+\frac12\ln n \r \\
&&&=\frac1{k} \l \ln ((kn-1)!) - \ln(k!) - (k(n-1)-1) \ln k+\frac12 \ln n \r \\
&&&=\frac1{k} \l \ln ((kn)! )  -\ln k -\ln n  - \ln(k!) - (k(n-1)-1) \ln k+\frac12\ln n \r \\
&&&= \frac1{k} \l \ln ((kn)! )   - \ln(k!) - (k(n-1)) \ln k - \frac12 \ln n\r \\
\Rightarrow && \ln ((kn)!) &\approx kn \ln n - kn + k + \ln(k!) + (k(n-1)) \ln k + \frac12 \ln n\\
\Rightarrow && (kn)! &\approx n^{kn+\frac12}e^{-k(n-1)}k!k^{k(n-1)} \\
&&&= n^{kn+\frac12} k! \l \frac{e}{k} \r^{k(1-n)}
\end{align*}

I would expect this approximation to be a better approximation for $(kn)!$ since it is created using a finer mesh.