A fun limit problem: bounding things however you like

有趣的求极限题：随心所欲的放缩 苏剑林 · 2015-03-28 · Mathematics inequality limit analysis

Yesterday a friend asked me the following problem, asking to prove:

$$\lim_{n\to\infty} \frac{1^n + 2^n +\dots + n^n}{n^n}=\frac{e}{e-1}$$

Let me quickly write down the solution.

Solution

First, notice that when $n$ is sufficiently large, the main contribution to

$$\frac{1^n + 2^n +\dots + n^n}{n^n}=\left(\frac{1}{n}\right)^n+\left(\frac{2}{n}\right)^n+\dots+\left(\frac{n}{n}\right)^n$$

comes from the last few terms, so we can compute it in reverse order

$$\begin{aligned}\frac{1^n + 2^n +\dots + n^n}{n^n}=&\left(\frac{1}{n}\right)^n+\left(\frac{2}{n}\right)^n+\dots+\left(\frac{n}{n}\right)^n\\ =&\left(\frac{n}{n}\right)^n+\dots+\left(\frac{2}{n}\right)^n+\left(\frac{1}{n}\right)^n\end{aligned}$$more

We have

$$\left(\frac{n-i}{n}\right)^n=\left(1-\frac{i}{n}\right)^n$$

which is an increasing function of $n$, so

$$\left(\frac{n-i}{n}\right)^n \leq \lim_{n\to\infty} \left(1-\frac{i}{n}\right)^n =e^{-i}$$

hence

$$\left(\frac{n}{n}\right)^n+\dots+\left(\frac{2}{n}\right)^n+\left(\frac{1}{n}\right)^n \leq e^0 + e^{-1}+e^{-2}+\dots=\frac{e}{e-1}$$

always holds.

On the other side, the main task is to find a lower bound estimate for $\left(\frac{n-i}{n}\right)^n$. We have

$$\begin{aligned}&\ln\left[\left(\frac{n-i}{n}\right)^n\right]\\ =&n\ln\left(1-\frac{i}{n}\right)\\ =&n\left[-\frac{i}{n}-\frac{1}{2}\left(\frac{i}{n}\right)^2-\frac{1}{3}\left(\frac{i}{n}\right)^3-\dots\right]\end{aligned}$$

Notice that we have the inequality $\ln(1-x) = -x -\frac{1}{2}x^2-\frac{1}{3}x^3-\dots > -x-x^2$ — of course, this inequality doesn't hold always, but it does hold when $x$ is small; roughly speaking, we can estimate that it holds when $0\leq x \leq \frac{1}{2}$. Therefore, when $i \leq \frac{n}{2}$, we have

$$\ln\left[\left(\frac{n-i}{n}\right)^n\right]\geq n\left[-\frac{i}{n}-\left(\frac{i}{n}\right)^2\right]=-i-\frac{i^2}{n}$$

or equivalently

$$\left(\frac{n-i}{n}\right)^n \geq e^{-i-i^2/n}\geq e^{-i} \left(1-\frac{i^2}{n}\right)\geq e^{-i} -\frac{i^2}{n}$$

Now, since we already know that $\sum_{i=0}^m i^2 \sim m^3$, we only need to keep the $i < n^{1/4}$ part, i.e.,

$$\begin{aligned}&\left(\frac{n}{n}\right)^n+\dots+\left(\frac{2}{n}\right)^n+\left(\frac{1}{n}\right)^n\\ \geq &\sum_{i=0}^{\left\lfloor n^{1/4} \right\rfloor}\left(1-\frac{i}{n}\right)^n\\ \geq &\sum_{i=0}^{\left\lfloor n^{1/4} \right\rfloor} \left(e^{-i} -\frac{i^2}{n}\right)\\ =&\frac{1-e^{-\left\lfloor n^{1/4} \right\rfloor-1}}{1-e^{-1}}-\lambda \frac{\left\lfloor n^{1/4} \right\rfloor ^3}{n}\end{aligned}$$

where $\lambda$ is some constant, whose specific value we don't need to know. Taking the limit, the latter term goes to 0, giving

$$\lim_{n\to\infty}\left(\frac{1}{n}\right)^n+\left(\frac{2}{n}\right)^n+\dots+\left(\frac{n}{n}\right)^n \geq\frac{e}{e-1}$$

Combining this with the inequality on the other side, we get

$$\lim_{n\to\infty}\left(\frac{1}{n}\right)^n+\left(\frac{2}{n}\right)^n+\dots+\left(\frac{n}{n}\right)^n = \frac{e}{e-1}$$

The whole process basically comes down to bounding things—and doing so however is convenient for us at each step, which of course is related to the fact that the problem itself is fairly weak. The derivation here isn't the most elegant or concise, but it's quite practical!