# What is $\lim_{n\to \infty}\sum_{k=1}^n \left(\frac{k}{n}\right)^n$? [duplicate]

I'm asked to find $\displaystyle\lim_{n\to \infty}\sum_{k=1}^n \left(\frac{k}{n}\right)^n$.

It seems that the sum converges.

I managed to prove that $\forall n,1<\sum_{k=1}^n \left(\frac{k}{n}\right)^n<e$

But I don't know how to prove convergence, nor find the value of the limit.

## marked as duplicate by YuiTo Cheng, Cesareo, kingW3, Adrian Keister, José Carlos Santos sequences-and-series StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jun 26 at 18:34

• You can turn this into $\displaystyle \lim_{n \to \infty} \left (\frac{1}{n}\right )^n H_n^{-n}$, but I'm not sure if this is easier. – UserX Sep 11 '14 at 16:49
• What is $H_n^{-n}$? – Idonknow Sep 11 '14 at 17:41
• – StubbornAtom Jan 23 at 14:03

Let $( b_{k,n} )_{k, n\in\mathbb{Z}_{+}}$ be the double sequence defined by

$$b_{k,n} = \begin{cases} 0,& n \le k\\ \left(1 - \frac{k}{n}\right)^n,& n \ge k\\ \end{cases}$$ We have $$\sum_{k=1}^n \left(\frac{k}{n}\right)^n = \sum_{k=0}^{n-1}\left(1 - \frac{k}{n}\right)^n = 1 + \sum_{k=1}^\infty b_{k,n}$$ This implies

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

If we fix $k$, then for any $n \ge k$, apply AM $\ge$ GM to the list of numbers consisting of $n$ copies of $1 - \frac{k}{n}$ and $1$ copy of $1$, we get

$$\left(1 - \frac{k}{n}\right)^{\frac{n}{n+1}} \le \frac{1}{n+1}\left[n\left(1-\frac{k}{n}\right) + 1\right] = 1 - \frac{k}{n+1} \quad\implies\quad b_{k,n} \le b_{k,n+1}$$

So for each fixed $k$, $b_{k,n}$ as a sequence of $n$ is non-negative and monotonic increasing. Furthermore, we know

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

By monotone convergence theorem for series${}^{\color{blue}{[1]}}$, we can exchange the limit and summation in $(*1)$ and get

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

Notes

• $\color{blue}{[1]}$ for the statement and a proof of monotone convergence theorem for series, see this.
• What am I missing here? I thought $\sum_{k=1}^\infty e^{-k} =\frac{1}{1-1/e}= \frac{e}{e-1}$, so shouldn't the result be $1+\frac{e}{e-1}$? – Scounged Aug 1 '15 at 21:16
• @Scounged $\sum_{k=\color{red}{a}}^\infty x^k = \frac{x^{\color{red}{a}}}{1-x}$ for $|x| < 1$. – achille hui Aug 1 '15 at 21:41
• Oh, I missed that $k=1$, and just assumed it was 0 for some reason. My bad. – Scounged Aug 1 '15 at 22:55

$$\lim_{n\rightarrow +\infty}\sum_{k=0}^n\left(\frac{k}{n}\right)^n=\lim_{n\rightarrow +\infty}\int_{\Bbb{N}_0}u_nd\nu=\int_{\Bbb{N}_0}e^{-k}d\nu(k)=\sum_{k=0}^{+\infty}e^{-k}=\frac{e}{e-1}$$

using the Monotone Convergence Theorem and as achille hui $$u_n=\begin{cases} 0,& n \le k\\ \left(1 - \frac{k}{n}\right)^n,& n \ge k\\ \end{cases}$$

• Can you expand a little bit more ? I edited things I thought were incorrect. – Gabriel Romon Sep 11 '14 at 18:22
• @G.T.R I misread the question, sorry. I edited my answer. – Krokop Sep 11 '14 at 18:54

Do you know what $(\frac{n-1}{n})^n$ approaches, and $(\frac{n-2}{n})^n$?

• It should be a comment ! – idm Sep 11 '14 at 16:48
• This hint leads directly to the sum $1+1/e+1/e^2+...$ – Empy2 Sep 11 '14 at 16:52
• Well, not directly (there is an exchange of limit and sum which needs some justification) but yes, it does lead to it. – Did Sep 11 '14 at 17:15
• It's not sufficient a hint. How do you prove that $\sum_{k=1}^{n-1} \left(\left(1-\frac{k}{n}\right)^n-\frac{1}{e^k}\right) \to 0$ ? – Gabriel Romon Sep 11 '14 at 17:48
• @G.T.R Monotonicity. – Daniel Fischer Sep 11 '14 at 17:56

It's easier to write the sum as $$\sum_{k = 0}^{n - 1} \bigg({n - k \over n}\bigg)^n = \sum_{k = 0}^{n - 1} \bigg(1 - {k \over n}\bigg)^n \tag 1$$ Note that $\ln (1 - {k \over n}) = -k/n - {1 \over 2}(k/n)^2 - ...$, so we have $$\ln \bigg(1 - {k \over n}\bigg) < -{k \over n}$$ Exponentiating both sides gives $$1 - {k \over n} < e^{-{k \over n}}$$ So taking $n$th powers we get $$\bigg(1 - {k \over n}\bigg)^n < e^{-k} \tag 2$$ Note also that since $\lim_{t \rightarrow 0} (1 + t)^{1 \over t} = e$, we also have $$\lim_{n \rightarrow \infty} \bigg(1 - {k \over n}\bigg)^n = \bigg(\lim_{n \rightarrow \infty} \bigg(1 - {k \over n}\bigg)^{n \over k}\bigg)^n$$ $$= e^{-k} \tag 3$$ So the limit of $(1)$ as $n \rightarrow \infty$ can be evaluated as follows. Fix some $N$. Then by $(3)$, the sum of the $k = 0$ through $k = N$ terms of the sum $(1)$ goes to $\sum_{k = 0}^N e^{-k}$ as $n$ goes to infinity, while by $(2)$ for any $n > N$ the sum of the remaining terms is between $0$ and $\sum_{k = N +1}^{\infty} e^{-k} = {\displaystyle {e^{-N - 1} \over 1 - {1 \over e}}}$. Hence we have $$\limsup_{n \rightarrow \infty} \sum_{k = 0}^n \bigg({n - k \over n}\bigg)^n \leq \limsup_{n \rightarrow \infty} \sum_{k = 0}^N \bigg({n - k \over n}\bigg)^n + {e^{-N - 1} \over 1 - {1 \over e}}$$ $$= \sum_{k = 0}^N e^{-k} + {e^{-N - 1} \over 1 - {1 \over e}}$$ $$\liminf_{n \rightarrow \infty} \sum_{k = 0}^n \bigg({n - k \over n}\bigg)^n \geq \liminf_{n \rightarrow \infty} \sum_{k = 0}^N \bigg({n - k \over n}\bigg)^n$$ $$\geq \sum_{k = 0}^N e^{-k}$$ Letting $N$ go to $\infty$ we get $$\lim_{n \rightarrow \infty} \sum_{k = 0}^n \bigg({n - k \over n}\bigg)^n = \sum_{k = 0}^\infty e^{-k}$$ $$={1 \over 1 - {1 \over e}}$$

• I think your proof is flawed. First you fix some $N$ that does not depend on $N$, and then you set $N=\lfloor n/2 \rfloor$. – Gabriel Romon Sep 12 '14 at 13:51
• I botched the end there, this should correct it. – Zarrax Sep 12 '14 at 23:56