13
$\begingroup$

Maybe, we can make use of Tannery's Theorem, or dominated convergence theorem, to exchange the order of the limit and summation:

\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[\left(1-\frac{k}{n}\right)^{n}\right]^{\frac{n-k}{n}}=\sum_{k=0}^{\infty}\lim_{n \to \infty}\left[\left(1-\frac{k}{n}\right)^{n}\right]^{\frac{n-k}{n}}=\sum_{k=0}^{\infty} e^{-k}=\frac{e}{e-1} \end{align*}

This is correct? How to verify that it satisfy the conditons of the theorem?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You have a sign error. $\endgroup$ – J.G. Mar 24 at 8:49
  • $\begingroup$ @J.G.: Thanks, fixed. $\endgroup$ – joriki Mar 24 at 8:58
  • 1
    $\begingroup$ Wonderful! Thanks a lot. $\endgroup$ – mengdie1982 Mar 24 at 9:26
  • 1
    $\begingroup$ It is an interesting answer. I liked it. $\endgroup$ – user0410 Mar 24 at 10:15
  • $\begingroup$ $\left(1-\frac kn\right)^{n-k}\le\left(1-\frac k{2k}\right)^{2k-k}$ is not so obvious. Can you give an explanation? $\endgroup$ – mengdie1982 Mar 24 at 12:53
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Strange, I tried splitting off the $\frac1n$ and thought it didn't work, but now I don't remember why I thought that :-). Why did you replace dominated convergence in your original answer by Tannery's theorem? $\endgroup$ – joriki Mar 24 at 23:08
  • 1
    $\begingroup$ @joriki: It seems to me that Tannery's Theorem is just DCT applied to sequences. Since I know there are simpler proofs of DCT when limited to sequences, I figured that was what Tannery was all about. I had never heard of it before this question. Let me know if you see any reason why step $(3)$ is not valid. It appears valid to me. $\endgroup$ – robjohn Mar 24 at 23:34
  • $\begingroup$ I hadn't heard about this theorem before, either. I think step $(3)$ is valid. $\endgroup$ – joriki Mar 25 at 1:43
  • $\begingroup$ Upvotes can be so unfair. Yours is really the better proof; I didn't find it because I made a mistake trying to go down that route; I found a nice other route, but it's more complicated; perhaps it looks a bit nicer because of the symmetry of the halves, but it requires more work than yours. $\endgroup$ – joriki Mar 25 at 2:12
  • 1
    $\begingroup$ @joriki: Your answer is nice and displays useful analytic methods. It was also written 12 hours prior. I am pleased with my answer and I think it will be useful to some people. I am not dismayed by the number of upvotes. $\endgroup$ – robjohn Mar 25 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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