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 $.

No comments:

Post a Comment