Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I remember that a couple of years ago a friend showed me and some other people the following expression:

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

As shown below, I can prove that this limit exists by the monotone convergence theorem. I also remember that my friend gave a very dubious "proof" that the value of the limit is $\frac{1}{e-1}$. I cannot remember the details of the proof, but I am fairly certain that it made the common error of treating $n$ as a variable in some places at some times and as a constant in other places at other times. Nevertheless, numerical analysis suggests that the value my friend gave was correct, even if his methods were flawed. My question is then:

What is the value of this limit and how do we prove it rigorously?

(Also, for bonus points, What might my friend's original proof have been and what exactly was his error, if any?)

I give my convergence proof below in two parts. In both parts, I define the sequence $a_n$ by $a_n=\frac{1^n+2^n+\cdots+(n-1)^n}{n^n}$ for all integers $n\ge 2$. First, I prove that $a_n$ is bounded above by $1$. Second, I prove that $a_n$ is increasing.

(1) The sequence $a_n$ satisfies $a_n<1$ for all $n\ge 2$.

Note that $a_n<1$ is equivalent to $1^n+2^n+\cdots+(n-1)^n<n^n$. I prove this second statement by induction. Observe that $1^2=1<4=2^2$. Now suppose that $1^n+2^n+\cdots+(n-1)^n<n^n$ for some integer $n\ge 2$. Then

$$1^{n+1}+2^{n+1}+\cdots+(n-1)^{n+1}+n^{n+1}\le(n-1)(1^n+2^n+\cdots+(n-1)^n)+n^{n+1}<(n-1)n^n+n^{n+1}<(n+1)n^n+n^{n+1}\le n^{n+1}+(n+1)n^n+\binom{n+1}{2}n^{n-1}+\cdots+1=(n+1)^{n+1}.$$

(2) The sequence $a_n$ is increasing for all $n\ge 2$.

We must first prove the following preliminary proposition. (I'm not sure if "lemma" is appropriate for this.)

(2a) For all integers $n\ge 2$ and $2\le k\le n$, $\left(\frac{k-1}{k}\right)^n\le\left(\frac{k}{k+1}\right)^{n+1}$.

We observe that $k^2-1\le kn$, so upon division by $k(k^2-1)$, we get $\frac{1}{k}\le\frac{n}{k^2-1}$. By Bernoulli's Inequality, we may find:

$$\frac{k+1}{k}\le 1+\frac{n}{k^2-1}\le\left(1+\frac{1}{k^2-1}\right)^n=\left(\frac{k^2}{k^2-1}\right)^n.$$

A little multiplication and we arrive at $\left(\frac{k-1}{k}\right)^n\le\left(\frac{k}{k+1}\right)^{n+1}$.

We may now first apply this to see that $\left(\frac{n-1}{n}\right)^n\le\left(\frac{n}{n+1}\right)^{n+1}$. Then we suppose that for some integer $2\le k\le n$, we have $\left(\frac{k}{n}\right)^n\le\left(\frac{k+1}{n+1}\right)^{n+1}$. Then:

$$\left(\frac{k-1}{n}\right)^n=\left(\frac{k}{n}\right)^n\left(\frac{k-1}{k}\right)^n\le\left(\frac{k+1}{n+1}\right)^{n+1}\left(\frac{k}{k+1}\right)^{n+1}=\left(\frac{k}{n+1}\right)^{n+1}.$$

By backwards (finite) induction from $n$, we have that $\left(\frac{k}{n}\right)^n\le\left(\frac{k+1}{n+1}\right)^{n+1}$ for all integers $1\le k\le n$, so:

$$a_n=\left(\frac{1}{n}\right)^n+\left(\frac{2}{n}\right)^n+\cdots+\left(\frac{n-1}{n}\right)^n\le\left(\frac{2}{n+1}\right)^{n+1}+\left(\frac{3}{n+1}\right)^{n+1}+\cdots+\left(\frac{n}{n+1}\right)^{n+1}<\left(\frac{1}{n+1}\right)^{n+1}+\left(\frac{2}{n+1}\right)^{n+1}+\left(\frac{3}{n+1}\right)^{n+1}+\cdots+\left(\frac{n}{n+1}\right)^{n+1}=a_{n+1}.$$

(In fact, this proves that $a_n$ is strictly increasing.) By the monotone convergence theorem, $a_n$ converges.

I should note that I am not especially well-practiced in proving these sorts of inequalities, so I may have given a significantly more complicated proof than necessary. If this is the case, feel free to explain in a comment or in your answer. I'd love to get a better grip on these inequalities in addition to finding out what the limit is.

Thanks!

share|improve this question

3 Answers 3

up vote 11 down vote accepted

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).

share|improve this answer
    
I think soon the Euler-Maclaurin formula will be renamed to Euler-Maclaurin-Spivey formula. :) +1. –  user17762 Nov 26 '12 at 1:26
    
@Marvis: I have used it in a lot of answers on this site! And thanks. :) –  Mike Spivey Nov 26 '12 at 1:26
2  
Yes. I will never forget math.stackexchange.com/questions/11726/… –  user17762 Nov 26 '12 at 1:27
    
@Marvis: I think that's probably the best answer I've ever given on this site. Certainly I spent enough time on it. :) –  Mike Spivey Nov 26 '12 at 2:46

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.

share|improve this answer
    
I think there's something wrong in $\sum_1^n \frac1 {1+k/n} \le \int_0^1 \frac {dx} {1+x}$ –  HLong Sep 29 at 4:23
    
@HLong: yes, you're right, the integral was intended to be $\int_{1}^{2}\frac{dx}{x+1}$, now fixed. –  Jack D'Aurizio Sep 29 at 12:34
    
No, you can see that $lim_{n \to \infty} \sum_{k=1}^n {\frac 1 {(n+k)}} = \int_0^1 \frac {dx} {1+x}=ln2$. So you can't evaluate the series. I think you should evaluate from $e.\frac {k^2.e^{-k}} {n+k}$ because $\sum_{k=1}^\infty k^2e^{-k}$ is convergent –  HLong Sep 29 at 15:50

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} $$

share|improve this answer
    
+1. Also, this proof appears in Finbarr Holland's follow-up (Mathematics Magazine 83 (1): 51-54, 2010) to my paper. He uses the AM-GM inequality to establish that $\left[1-\frac{k}{n}\right]_+^n$ is a non-decreasing function of $n$. –  Mike Spivey Nov 26 '12 at 16:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.