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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s