Find $\lim\limits_{n \to \infty}\sum_{k=1}^n\left(\frac{k}{n}\right)^k$.

Solution 1:

As your preliminary calculation shows, the upper half of the terms yields the same sum in the limit, whereas the sum of the lower half goes to zero. We can apply Tannery’s theorem separately to each half:

$$ \sum_{k=1}^n\left(\frac kn\right)^k=\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left(\frac kn\right)^k+\sum_{k=\left\lceil\frac n2\right\rceil}^n\left(\frac kn\right)^k\;. $$

For the lower half,

$$ \left(\frac kn\right)^k\le\left(\frac12\right)^k\quad\text{and}\quad\lim_{n\to\infty}\left(\frac kn\right)^k=0 $$

so Tannery’s theorem applies with $\sum_{k=1}^\infty\left(\frac12\right)^k=1\lt\infty$, yielding

$$ \lim_{n\to\infty}\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left(\frac kn\right)^k=\sum_{k=1}^\infty\lim_{n\to\infty}\left(\frac kn\right)^k=0\;. $$

For the upper half, we can apply your transformation of the summation index to write it as

$$ \sum_{k=\left\lceil\frac n2\right\rceil}^n\left(\frac kn\right)^k=\sum_{k=0}^{n-\left\lceil\frac n2\right\rceil}\left(1-\frac kn\right)^{n-k}\;. $$

Differentiating the logarithm of the summand with respect to $n$ yields $\log\left(1-\frac kn\right)+\frac kn\le0$. Since the terms decrease with $n$ and $n\ge2k$, we obtain an upper bound for $n=2k$. Thus, in this half,

$$ \left(1-\frac kn\right)^{n-k}\le\left(1-\frac k{2k}\right)^{2k-k}=\left(\frac12\right)^k\quad\text{and}\quad\lim_{n\to\infty}\left(1-\frac kn\right)^{n-k}=\mathrm e^{-k}\;, $$

so Tannery’s theorem applies with $\sum_{k=0}^\infty\left(\frac12\right)^k=2\lt\infty$, yielding

$$ \lim_{n\to\infty}\sum_{k=0}^{n-\left\lceil\frac n2\right\rceil}\left(1-\frac kn\right)^{n-k}=\sum_{k=0}^\infty\lim_{n\to\infty}\left(1-\frac kn\right)^{n-k}=\sum_{k=0}^\infty {\mathrm e}^{-k}=\frac{\mathrm e}{\mathrm e-1}\;. $$

Together, this shows that

$$ \lim_{n\to\infty}\sum_{k=1}^n\left(\frac kn\right)^k=\frac{\mathrm e}{\mathrm e-1}\;. $$

Solution 2:

Answer Using Tannery's Theorem and Bernoulli's Inequality

Note that $\left(\frac{n-k}n\right)^{n-k}$ is decreasing in $n$ for $n\gt k$. A proof using Bernoulli's Inequality is given below. $$ \begin{align} \lim_{n\to\infty}\sum_{k=1}^n\left(\frac{k}{n}\right)^k &=\lim_{n\to\infty}\sum_{k=0}^{n-1}\left(\frac{n-k}{n}\right)^{n-k}\tag1\\ &=\lim_{n\to\infty}\frac1n+\lim_{n\to\infty}\sum_{k=0}^{n-2}\left(\frac{n-k}{n}\right)^{n-k}\tag2\\ &=0+\sum_{k=0}^\infty e^{-k}\tag3\\[3pt] &=\frac{e}{e-1}\tag4 \end{align} $$ Explanation:
$(1)$: substitute $k\mapsto n-k$
$(2)$: isolate the $k=n-1$ term
$(3)$: each term in the sum is no greater than $\left(\frac2{k+2}\right)^2$
$\phantom{(4)\text{:}}$ so we can apply Tannery's Theorem,
$\phantom{(4)\text{:}}$ which is Dominated Convergence for Series $\left(\ell^1\right)$
$(4)$: sum the geometric series

More Detail on Step $\boldsymbol{(3)}$

Step $(3)$ is a bit tricky. We isolate the $k=n-1$ term so that the terms in the remaining sum are no greater than $\left(\frac2{k+2}\right)^2$. For $n\lt k+2$, the terms are $0$ (or missing). For $n=k+2$, the term is $$ \left(\frac{n-k}{n}\right)^{n-k}=\left(\frac2{k+2}\right)^2\tag5 $$ For $n\ge k+2$, $\left(\frac{n-k}{n}\right)^{n-k}$ decreases, as shown below, from $\left(\frac2{k+2}\right)^2$ to $e^{-k}$.

We can then apply Tannery's Theorem because $\sum\limits_{k=0}^\infty\left(\frac2{k+2}\right)^2\lt\infty$.

Bernoulli says $\boldsymbol{\left(\frac{n-k}n\right)^{n-k}}$ is Decreasing in $\boldsymbol{n}$ $$ \begin{align} \frac{\left(\frac{n-k}n\right)^{n-k}}{\left(\frac{n-k+1}{n+1}\right)^{n-k+1}} &=\frac{n}{n-k}\left(\frac{n-k}n\frac{n+1}{n-k+1}\right)^{n-k+1}\tag6\\ &=\frac{n}{n-k}\left(1-\frac{k}{(n-k+1)n}\right)^{n-k+1}\tag7\\[3pt] &\ge\frac{n}{n-k}\left(1-\frac{k}{n}\right)\tag8\\[9pt] &=1\tag9 \end{align} $$ Explanation:
$(6)$: algebra
$(7)$: algebra
$(8)$: Bernoulli's Inequality
$(9)$: algebra