I can show that the following limit exists but I am having difficulties to find it. It is $$\lim_{n\to \infty} \sum_{k=1}^n \frac{k^n}{n^n}$$ Can someone please help me?
How to evaluate $ \lim \limits_{n\to \infty} \sum \limits_ {k=1}^n \frac{k^n}{n^n}$?
-
0How could you show that the limit exist? – 2012-06-28
-
1@Siminore: The sum is very similar to $\int_{0}^{1}x^xdx$. Isn't it? – 2012-06-28
-
0Numerically, for $n=1000$, I get 1.58098. – 2012-06-28
-
0@Siminore: That happens to be only a little shy of the correct answer, $\dfrac{1}{1 - 1/e}$. – 2012-06-28
-
0Probably. But the result is not $\int_0^1 x^x\, dx$. – 2012-06-28
5 Answers
An asymptotic expansion can be obtained as below. More terms can be included by using more terms in the expansions of $\exp$ and $\log$. $$ \begin{align} \sum_{k=0}^n\frac{k^n}{n^n} &=\sum_{k=0}^n\left(1-\frac{k}{n}\right)^n\\ &=\sum_{k=0}^n\exp\left(n\log\left(1-\frac{k}{n}\right)\right)\\ &=\sum_{k=0}^{\sqrt{n}}\exp\left(n\log\left(1-\frac{k}{n}\right)\right)+O\left(ne^{-\sqrt{n}}\right)\\ &=\sum_{k=0}^{\sqrt{n}}\exp\left(-k-\frac{1}{2n}k^2+O\left(\frac{k^3}{n^2}\right)\right)+O\left(ne^{-\sqrt{n}}\right)\\ &=\sum_{k=0}^{\sqrt{n}}e^{-k}\exp\left(-\frac{1}{2n}k^2+O\left(\frac{k^3}{n^2}\right)\right)+O\left(ne^{-\sqrt{n}}\right)\\ &=\sum_{k=0}^{\sqrt{n}}e^{-k}\left(1-\frac{1}{2n}k^2+O\left(\frac{k^ 4}{n^2}\right)\right)+O\left(ne^{-\sqrt{n}}\right)\\ &=\sum_{k=0}^{\sqrt{n}}e^{-k}-\frac{1}{2n}\sum_{k=0}^{\sqrt{n}}k^2e^{-k}+O\left(\frac{1}{n^2}\right)\\ &=\frac{e}{e-1}-\frac{1}{2n}\frac{e(e+1)}{(e-1)^3}+O\left(\frac{1}{n^2}\right) \end{align} $$ Several steps use $$ \sum_{k=n}^\infty e^{-k}k^m=O(e^{-n}n^m) $$ which decays faster than any power of $n$.
-
0Why $$\sum\limits_{k=0}^n e^{-k}O\left(\frac{k^4}{n^2}\right)=O\left(\frac{1}{n^2}\right)$$ ? – 2012-06-28
-
0@Norbert: Because $$\sum_{k=0}^ne^{-k}O\left(\frac{k^4}{n^2}\right)\le\left(\sum_{k=0}^\infty e^{-k}k^4\right)O\left(\frac{1}{n^2}\right)$$ ! – 2012-06-28
-
0Thakns, I'll try to learn $O$-approach in future. – 2012-06-28
-
0I personally think that $\ln(1-x)=-x-x^2/2+O(x^3)$ only holds for $x\prec1$, so you should break the summation into $0
d(n)$, where $d(n)\prec n$. PS: $f(n)\prec g(n)\iff\lim_{n\to\infty}f(n)/g(n)=0$. – 2012-06-29 -
0Good approximation, where $\Theta_n(t)$ is not needed. – 2012-06-29
-
0@FrankScience: Done. I did indeed forget the tail, which dies almost exponentially. – 2012-06-29
-
0This still isn't quite correct. You can't use a Taylor expansion of $\log(1-k/n)$, because the upper bound on $k/n$ does not go to 0 as $n\to\infty$. However if you split the tail at e.g. $\lfloor\sqrt n\rfloor$, this works. – 2012-06-29
-
0@GenericHuman I've mentioned, see preceding comment. – 2012-06-29
-
0@robjohn LOL. Omit the tail, just like the answer on *Concrete Mathematics*, which made me misunderstood for a long time. – 2012-06-29
-
0@FrankScience: Yes, I hadn't really read your comment since robjohn said he had addressed the problem (plus $d(n)\prec n$ looks a lot like $d(n)
$d(n)=o(n)$ ). – 2012-06-29 -
0@GenericHuman I thought about using $o(f(n))$, but eventually I used $\prec$ because both $O$ and $o$ appear seems ambiguous. – 2012-06-29
-
0@GenericHuman: For $0\le x\le\frac12$, $\left|\log(1-x)+x+x^2/2\right|\le x^3$, so $\log(1-x)=-x-x^2/2+O(x^3)$. The Taylor series for $\log$ is fine. I did have to adjust the upper limit of the sum for $\exp\left(-\frac{1}{2n}k^2+O\left(\frac{k^3}{n^2}\right)\right)$ – 2012-06-29
-
0I really like this answer, Rob. I published a paper on this sum several years ago (see, for example, [here](http://math.stackexchange.com/questions/244657/value-of-lim-n-to-infty-frac1n2n-cdotsn-1nnn/244663#244663), and I've kept my eye out for alternative ways of getting the limiting expression. Your answer here is one of my favorites. It does a really nice job of handling the error terms. – 2013-01-09
-
0@MikeSpivey: Thanks! I am a big fan of the Euler-Maclaurin Sum Formula. For polynomials, it is exact (in fact, in [this answer](http://math.stackexchange.com/a/156085), I give a condition for the EMS Formula to converge). – 2013-01-09
Finally, I have suffered this proof. Consider functions $$ f_n(x)=\left(1-\frac{\lfloor x\rfloor}{n}\right)^n\chi_{[0,n+1]}(x) $$ Note that $$ \int\limits_{[0,+\infty)} f_n(x)d\mu(x)=\sum\limits_{k=0}^n\int\limits_{[k,k+1)}\left(1-\frac{\lfloor x\rfloor}{n}\right)^nd\mu(x)= \sum\limits_{k=0}^n\left(1-\frac{k}{n}\right)^n $$ $$ \lim\limits_{n\to\infty}f_n(x)=\lim\limits_{n\to\infty}\left(1-\frac{\lfloor x\rfloor}{n}\right)^n\cdot \lim\limits_{n\to\infty}\chi_{[0,n+1]}(x)=e^{\lfloor x\rfloor} $$ One may check that $\{f_n:n\in\mathbb{N}\}$ is a non-decreasing sequence of non-negative functions, then using monotone convergence theorem we get $$ \lim\limits_{n\to\infty}\sum\limits_{k=0}^n\left(\frac{k}{n}\right)^n= \lim\limits_{n\to\infty}\sum\limits_{k=0}^n\left(1-\frac{k}{n}\right)^n= \lim\limits_{n\to\infty}\int\limits_{[0,+\infty)} f_n(x)d\mu(x)= $$ $$ \int\limits_{[0,+\infty)} \lim\limits_{n\to\infty}f_n(x)d\mu(x)= \int\limits_{[0,+\infty)} e^{\lfloor x\rfloor}d\mu(x)= \sum\limits_{k=0}^\infty e^{-k}=\frac{1}{1-e^{-1}} $$
-
1You must justify the interchange of the limit and the sum in the second equality. One way to do this is to note that $(1-k/m)^m<(1-k/n)^n$ if $k+1\leq m
– 2012-06-28 -
0You could just use the sequence version of the [Monotone Convergence Theorem](http://en.wikipedia.org/wiki/Monotone_convergence_theorem). – 2012-06-28
-
0Thanks, I didn't knew that – 2012-06-28
-
0Could you compute the asymptotics, not just the limits. I'm very interested in such theory. – 2012-06-28
-
0@FrankScience Why don't you use [Euler–Maclaurin formula](http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula)? – 2012-06-28
-
0@Norbert Because yesterday I thought [Poisson summation formula](http://en.wikipedia.org/wiki/Poisson_summation_formula) is more powerful in this problem than Euler-Maclaurin summation formula, where $\Theta_n(t)$ is periodic function of $t$. – 2012-06-29
Let's notice a few things. All the terms are positive, bounded between $0$ and $1$, and there is a term that is exactly $1$. What about the next largest term?
So we ask ourselves what $\lim \limits_{n \to \infty} \left( \dfrac{n-1}{n} \right)^n$ is, and after a little calculation we see that this limit is $1/e$. The 'next' term involves $\lim \limits_{n \to \infty} \left( \dfrac{n-2}{n} \right)^n = e^{-2}$. So heuristically, we would expect the limit to be
$$1 + e^{-1} + e^{-2} + \dots = \frac{1}{1-\frac{1}{e}}$$
Working only a little harder, you can justify that this is the limit.
-
0I wonder if it is possible to prove that $$\lim_{n \to +\infty} \sum_{k=1}^n \left( \frac{k^n}{n^n}-e^{-k} \right)=0.$$ – 2012-06-28
-
0Sorry: the limit should be 1, in the previous comment. – 2012-06-28
-
0@Siminore: Have you tried? It's really not bad at all, as long as you know the dominated convergence theorem and/or the monotone convergence theorem. In fact, that series is absolutely convergent, so you can do a whole lot of things to it – 2012-06-28
-
0Yes, it's a matter of passing to the limit inside a series. – 2012-06-28
Just for reference: With aid of some fancy theorem, you can skip most of hard analysis. As in other answers, we begin by writing
$$ \sum_{k=1}^{n} \left( \frac{k}{n}\right)^n \ \overset{k \to n-k}{=} \ \sum_{k=0}^{n-1} \left( 1 - \frac{k}{n}\right)^n \ = \ \sum_{k=0}^{\infty} \left( 1 - \frac{k}{n}\right)^n \mathbf{1}_{\{k < n\}}, $$
where $\mathbf{1}_{\{k < n\}}$ is the indicator function which takes value $1$ if $k < n$ and $0$ otherwise. Now for each $0 \leq k < n$, utilizing the inequality $\log(1-x) \leq -x$ which holds for all $x \in [0,1)$ shows that
$$ \left( 1 - \frac{k}{n}\right)^n = e^{n \log(1 - \frac{k}{n})} \leq e^{-k}. $$
Since $\sum_{k=0}^{\infty} e^{-k} < \infty$, by the dominated convergence theorem we can interchange the infinite sum and the limit:
$$ \lim_{n\to\infty} \sum_{k=1}^{n} \left( \frac{k}{n}\right)^n = \sum_{k=0}^{\infty} \lim_{n\to\infty} \left( 1 - \frac{k}{n}\right)^n \mathbf{1}_{\{k < n\}} = \sum_{k=0}^{\infty} e^{-k} = \frac{1}{1 - e^{-1}}. $$
-
1Ah, so *this* is what mixedmath was alluding to. Very nicely done. (+1) – 2017-09-27
-
0Maybe this is a basic question, but how did you get the first equality? – 2017-09-27
-
0@user372003, I added a bit of details to my answer. But basically, I replaced the index $k$ by $n-k$. – 2017-09-27
$\sum_{k=1}^n(k/n)^n=\sum_{0 Can anybody give a more accurate approximation?
The key to the approximation is to find the asymptotics for $\sum_{k>0}\exp(-k-k^2/2n)$, like the Bell sum $\sum_{k>0}e^{-k^2/n}$. Edit anon pointed out that it's theta function: $\sum_ke^{-(k+t)^2/n}$, so the Fourier series works pretty well for the asymptotics:
$$\Theta_n(t)=\sqrt{\pi n}\left(1+2e^{-\pi^2 n}(\cos2\pi t)+2e^{-4\pi^2 n}(\cos4\pi t)+2e^{-9\pi^2 n}(\cos6\pi t)+\cdots\right)$$
But I have no idea about Fourier series because I know very little about calculus!
-
0In [my answer](http://math.stackexchange.com/a/164269), I show how to get more accuracy by including more terms in in the series for $\log$ and $\exp$. – 2012-06-28
-
0@robjohn Thanks. – 2012-06-29