## Saturday, November 25, 2006

### Stirling Silver. Topic: Calculus.

Problem: Evaluate $\displaystyle \lim_{n \rightarrow \infty} \frac{k^n \cdot n!}{n^n}$ where $k$ is an arbitrary positive real number.

Solution: Well in its current form the limit does not look very fun, so let's take the natural log of it.

$\displaystyle \ln{L_k} = \lim_{n \rightarrow \infty} \left(n \ln{k}+\sum_{i=1}^n \ln{i}-n\ln{n}\right)$

where $L_k$ is the limit in question. Let's bound the summation term on the RHS using integrals. We see that

$\displaystyle \int_1^n \ln{x} dx \le \sum_{i=1}^n \ln{i} \le \int_1^n \ln{x}dx + \ln{n}$

$\displaystyle n\ln{n}-n \le \sum_{i=1}^n \ln{i} \le n\ln{n}-n+\ln{n}$

because $\displaystyle \int \ln{x} dx = x\ln{x}-x$. Plugging this back into the equation, we get

$\displaystyle \lim_{n \rightarrow \infty} n(\ln{k}-1) \le \ln{L_k} \le \lim_{n \rightarrow \infty} n(\ln{k}-1)+\ln{n}$.

For $k < e$, the coefficient of the $n$ term is negative and it dominates the $\ln{n}$ term, so as $n \rightarrow \infty$ both the upper and lower bounds approach $- \infty$, hence $\ln{L_k} \rightarrow -\infty \Rightarrow L_k \rightarrow 0$.

For $k > e$, the coefficient on the $n$ term is positive, so both the upper and lower bounds approach $\infty$ so $\ln{L_k} \rightarrow \infty \Rightarrow L_k \rightarrow \infty$.

Now for the trickier case $k = e$. Consider a midpoint approximation of the area under the curve $\ln{x}$ from $\frac{1}{2}$ to $n+\frac{1}{2}$. Since $\ln{x}$ is concave, the midpoint approximation will be larger than the integral (draw a picture to see this). So

$\displaystyle \int_{\frac{1}{2}}^{n+\frac{1}{2}} \ln{x}dx \le \sum_{i=1}^n \ln{i}$.

But the LHS turns out to be

$\left(n+\frac{1}{2}\right)\ln{\left(n+\frac{1}{2}\right)}-\left(n+\frac{1}{2}\right)-\frac{1}{2}\ln{\frac{1}{2}}+\frac{1}{2}$

which we can bound below by

$n\ln{n}+\frac{1}{2}\ln{n}-n+C$

for some arbitrary constant $C$. Then

$\displaystyle \sum_{i=1}^n \ln{i} \ge n\ln{n}+\frac{1}{2}\ln{n}-n+C$.

Plugging back into our original expression for $\ln{L_k}$, we obtain

$\ln{L_e} \ge \lim_{n\rightarrow \infty} (n+n\ln{n}+\frac{1}{2}\ln{n}-n+C-n\ln{n}) = \lim_{n\rightarrow \infty} (\frac{1}{2}\ln{n}+C) = \infty$

so $L_e \rightarrow \infty$ as well. Hence if $k < e$, the limit converges to zero and if $k \ge e$ the limit diverges to $\infty$. QED.

--------------------

Comment: This limit it very interesting because it gives us an idea about Stirling's approximation. In fact, from the last inequality, we see that $L_e \sim \sqrt{n}$ and we have

$n! \sim \left(\frac{n}{e}\right)^n \cdot \sqrt{n}$.

A very good approximation is

$n! \approx \sqrt{\pi \cdot \left(2n+\frac{1}{3}\right)} \cdot \left(\frac{n}{e}\right)^n$.