Value of $\lim_{n\to \infty}\frac{1^n+2^n+\cdots+(n-1)^n}{n^n}$

Solution 1:

The limit is $\frac{1}{e-1}$. I wrote a paper on this sum several years ago and used the Euler-Maclaurin formula to prove the result. The paper is "The Euler-Maclaurin Formula and Sums of Powers," Mathematics Magazine, 79 (1): 61-65, 2006. Basically, I use the Euler-Maclaurin formula to swap the sum with the corresponding integral. Then, after some asymptotic analysis on the error term provided by Euler-Maclaurin we get $$\lim_{n\to \infty}\frac{1^n+2^n+\cdots+(n-1)^n}{n^n} = \sum_{k=0}^{\infty} \frac{B_k}{k!},$$ where $B_k$ is the $k$th Bernoulli number. The exponential generating function of the Bernoulli numbers then provides the $\frac{1}{e-1}$ result.

I should mention that I made a mistake in the original proof, though! The correction, as well as the generalization $$\lim_{n\to \infty}\frac{1^n+2^n+\cdots+(n+k)^n}{n^n} = \frac{e^{k+1}}{e-1}$$ are contained in a letter to the editor (Mathematics Magazine 83 (1): 54-55, 2010).

Solution 2:

We can write $a_n=\sum_{k=1}^{n-1}\left(1-\frac{k}{n}\right)^n$. The given limit can then be written in the form $$ \lim_{n\to\infty}\sum_{k=1}^\infty\left[1-\frac{k}{n}\right]_+^n $$ (where $[x]_+$ is the positive part, i.e., $[x]_+=x$ if $x\geq0$, $0$ otherwise).

I claim that for fixed $k$, $\left[1-\frac{k}{n}\right]_+^n$ is a non-decreasing function of $n$. This means we can pass the limit inside the sum. The limiting value of the $k$-th term is $e^{-k}$, so the value of the limit is $$ \sum_{k=1}^\infty e^{-k}=\frac{1}{e-1} $$

Solution 3:

We can prove this by simple squeezing. Using the fact that $A>B>0$ implies $A^n-B^n \leq n(A-B)A^{n-1}$, and the facts that $e^{-x}\leq\frac{1}{1+x},e^x\geq 1+x+\frac{x^2}{2}$, we have:

$$ e^{-k} - \left(1-\frac{k}{n}\right)^n \leq n\left(e^{-k/n}-1+\frac{k}{n}\right)e^{-k\,\frac{n-1}{n}}\leq e\cdot\frac{k^2 e^{-k}}{n+k}\leq \frac{2e}{n+k},$$

so:

$$\sum_{k=1}^{n}\left(e^{-k}-\left(1-\frac{k}{n}\right)^n\right)\leq \frac{2e}{n}\sum_{k=1}^{n}\frac{1}{1+k/n}\leq\frac{2e}{n}\int_{1}^{2}\frac{dx}{1+x}<\frac{9}{4n},$$

then:

$$\lim_{n\to+\infty}\sum_{k=1}^{n}\left(1-\frac{k}{n}\right)^n=\lim_{n\to+\infty}\sum_{k=1}^{n}e^{-k} = \frac{e}{e-1}, $$

no need to use any advanced technique.