An Interesting Limit Problem: Scaling at Will

By 苏剑林 | March 28, 2015

Yesterday, a friend asked me the following problem, to prove: \[\lim_{n\to\infty} \frac{1^n + 2^n +\dots + n^n}{n^n}=\frac{e}{e-1}\] I am briefly recording the solution process here.

Solution

First, it can be noted that when $n$ is sufficiently large, \[\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\] the main terms are concentrated in the last few terms. Therefore, we can calculate it in reverse: \[\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}\] And since we have \[\left(\frac{n-i}{n}\right)^n=\left(1-\frac{i}{n}\right)^n\] which is an increasing function with respect to $n$, we have \[\left(\frac{n-i}{n}\right)^n \leq \lim_{n\to\infty} \left(1-\frac{i}{n}\right)^n =e^{-i}\] Thus, \[\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}\] holds constantly.

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 is not universally true, but it holds when $x$ is small. We can roughly 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 \[\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, we already know that $\sum_{i=0}^m i^2 \sim m^3$, so we only take the part where $i < n^{1/4}$. That is to say \[\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}\]

$\lambda$ is a constant, and we do not need to know its specific value. Taking the limit, the latter term becomes 0, yielding \[\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 other side of the inequality, 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 entire process primarily involves scaling, and scaling "at will" according to our needs—of course, this is related to the fact that the problem itself is relatively "weak." The process in this article is not the most concise or elegant, but it is quite practical!

,
        author={苏剑林},
        year={2015},
        month={Mar},
        url={\url{https://kexue.fm/archives/3256}},
}