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

Solution 1:

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 (on web-archive).

Solution 2:

Answer changed

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

Solution 3:

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

Solution 4:

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