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$
8
  • 1
    $\begingroup$ So maybe not exactly a duplicate but math.stackexchange.com/questions/164074/… has most of the same ideas. $\endgroup$ Mar 24 '20 at 4:19
  • $\begingroup$ And math.stackexchange.com/questions/927771/… $\endgroup$ Mar 24 '20 at 4:20
  • 1
    $\begingroup$ Not the same. The power is $k$ not $n$. $\endgroup$ Mar 24 '20 at 4:23
  • 1
    $\begingroup$ I know, that's why I retracted my close vote. But the limit is the same and the analysis is 90% the same. $\endgroup$ Mar 24 '20 at 4:25
  • $\begingroup$ I wonder if Stirling's approximation could be valuable on $k^k$. $\endgroup$
    – zugzug
    Mar 24 '20 at 4:51
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$
7
  • $\begingroup$ You have a sign error. $\endgroup$
    – J.G.
    Mar 24 '20 at 8:49
  • $\begingroup$ @J.G.: Thanks, fixed. $\endgroup$
    – joriki
    Mar 24 '20 at 8:58
  • 1
    $\begingroup$ Wonderful! Thanks a lot. $\endgroup$ Mar 24 '20 at 9:26
  • 1
    $\begingroup$ It is an interesting answer. I liked it. $\endgroup$
    – user0410
    Mar 24 '20 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$ Mar 24 '20 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$
6
  • $\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 '20 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 '20 at 23:34
  • $\begingroup$ I hadn't heard about this theorem before, either. I think step $(3)$ is valid. $\endgroup$
    – joriki
    Mar 25 '20 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 '20 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 '20 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.