# Limit of (1^n + 2^n + … + n^n)/n^n

We have all seen this easy exercise: show that $\displaystyle \lim_{n\to\infty} \frac{1}{n^{\alpha + 1}}\sum_{k=1}^n k^{\alpha}=\frac{1}{\alpha +1},$ where $\alpha > -1$ is a real constant, i.e. $\alpha$ is independent of $n.$ The proof is quite simple: we have

$\displaystyle \lim_{n\to\infty} \frac{1}{n^{\alpha + 1}}\sum_{k=1}^n k^{\alpha}= \lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^n \left(\frac{k}{n}\right)^{\alpha}=\int_0^1 x^{\alpha}dx=\frac{1}{\alpha+1}.$

But things get interesting when $\alpha$ depends on $n.$
For example, what is $\displaystyle \lim_{n\to\infty} \frac{1}{n^{n + 1}} \sum_{k=1}^n k^n?$ Well, the answer is $0$ and that’s a trivial consequence of a much nicer result that we are going to prove in Problem 2. But first, we need to prove something, which is nice by itself.

Problem 1. If $r$ is a real constant, show that $\displaystyle \lim_{n\to\infty} \sum_{k=1}^{n-1} \frac{k^re^{-k}}{n-k}=0.$

Solution. Choose an integer $m \ge 0$ such that $r \le m.$ Then

$\displaystyle e^k > \frac{k^{m+1}}{(m+1)!} \ge \frac{k^{r+1}}{(m+1)!}$

and so

\displaystyle \begin{aligned} 0 < \sum_{k=1}^{n-1} \frac{k^re^{-k}}{n-k} < (m+1)! \sum_{k=1}^{n-1} \frac{1}{k(n-k)}=\frac{2(m+1)!}{n}\sum_{k=1}^{n-1}\frac{1}{k} < \frac{2(m+1)!}{n}\sum_{k=1}^n\frac{1}{k} \\ =\frac{2(m+1)!}{n}\left(\sum_{k=1}^n\frac{1}{k}-\ln n \right) + \frac{2(m+1)! \ln n}{n}. \end{aligned}

Now the result follows from the facts that

$\displaystyle \lim_{n\to\infty} \frac{1}{n}\left(\sum_{k=1}^n\frac{1}{k}-\ln n \right)=\lim_{n\to\infty}\frac{1}{n}\gamma=0,$

where $\gamma$ is the Euler’s constant, and $\displaystyle \lim_{n\to\infty} \frac{\ln n}{n}=0. \ \Box$

Problem 2. Show that $\displaystyle \lim_{n\to\infty} \frac{1}{n^n}\sum_{k=1}^n k^n=\frac{e}{e-1}.$

Solution. Let $\displaystyle a_n:= \frac{1}{n^n}\sum_{k=1}^n k^n.$ By the Example in this post, we have

$\displaystyle e^{\frac{x}{1+x}} \le 1+ x \le e^x, \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

for $x > -1.$ Thus

$\displaystyle a_n =\sum_{k=1}^n \left(\frac{k}{n}\right)^n=\sum_{k=0}^{n-1} \left(1-\frac{k}{n}\right)^n\le \sum_{k=0}^{n-1}e^{-k} < \sum_{k=0}^{\infty}e^{-k}=\frac{e}{e-1}.$

On the other hand, again by $(*),$ we have

\displaystyle \begin{aligned} a_n=\sum_{k=0}^{n-1} \left(1-\frac{k}{n}\right)^n \ge \sum_{k=0}^{n-1} e^{\frac{-kn}{n-k}}=\sum_{k=0}^{n-1}e^{-k} - \sum_{k=0}^{n-1} \left(1-e^{\frac{-k^2}{n-k}} \right)e^{-k} \ge \sum_{k=0}^{n-1}e^{-k} - \sum_{k=0}^{n-1} \frac{k^2e^{-k}}{n-k}. \end{aligned}

So we have proved that

$\displaystyle \sum_{k=0}^{n-1}e^{-k} - \sum_{k=0}^{n-1} \frac{k^2e^{-k}}{n-k} \le a_n < \frac{e}{e-1},$

which completes the solution because $\displaystyle \lim_{n\to\infty} \sum_{k=0}^{n-1}e^{-k}=\sum_{k=0}^{\infty}e^{-k}=\frac{e}{e-1}$ and, by Problem 1, $\displaystyle \lim_{n\to\infty} \sum_{k=0}^{n-1} \frac{k^2e^{-k}}{n-k}=0$ and so, by the squeeze theorem, $\displaystyle \lim_{n\to\infty} a_n = \frac{e}{e-1}. \ \Box$

Remark. There is another proof of Problem 2 that uses Tannery’s theorem.

Example. Show that $\displaystyle \lim_{n\to\infty} \sum_{i=0}^n \binom{n+1}{i}\frac{B_i}{n^i}=\frac{1}{e-1},$ where $B_i$ are Bernoulli numbers.

Solution. In the problem in this post, put $k=n$ to get

$\displaystyle \sum_{i=1}^ni^n=\frac{n^{n+1}}{n+1}\sum_{i=0}^n \binom{n+1}{i}\frac{b_i}{n^i}.$

Thus, since $\displaystyle b_1=-B_1=\frac{1}{2}$ and $b_i=B_i$ for $i \ne 1,$ we have

$\displaystyle \frac{n+1}{n^{n+1}}\displaystyle \sum_{i=1}^ni^n=\sum_{i=0}^n \binom{n+1}{i}\frac{B_i}{n^i}+\frac{n+1}{n}$

and the result follows because, by Problem 2,

$\displaystyle \lim_{n\to\infty}\frac{n+1}{n^{n+1}}\displaystyle \sum_{i=1}^ni^n=\lim_{n\to\infty}\frac{1}{n^n}\displaystyle \sum_{i=1}^ni^n=\frac{e}{e-1}. \ \Box$

Exercise 1. If $\alpha \le -1$ is a real constant, what is $\displaystyle \lim_{n\to\infty} \frac{1}{n^{\alpha+1}} \sum_{k=1}^n k^{\alpha}?$

Exercise 2. Show that $\displaystyle \lim_{n\to\infty} \frac{1}{n^{n+1}} \sum_{k=1}^n k^n =0$ without using the result given in Problem 2.
Hint. You’ll only need the easy half of the solution of Problem 2.