# How to evaluate $\lim \limits_{n\to \infty} \sum \limits_ {k=1}^n \frac{k^n}{n^n}$?

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 could you show that the limit exist? – Babak S. Jun 28 '12 at 8:25
@Siminore: The sum is very similar to $\int_{0}^{1}x^xdx$. Isn't it? – Babak S. Jun 28 '12 at 8:40
Numerically, for $n=1000$, I get 1.58098. – Siminore Jun 28 '12 at 8:44
@Siminore: That happens to be only a little shy of the correct answer, $\dfrac{1}{1 - 1/e}$. – mixedmath Jun 28 '12 at 8:50
Probably. But the result is not $\int_0^1 x^x\, dx$. – Siminore Jun 28 '12 at 9:01

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

-
Why $$\sum\limits_{k=0}^n e^{-k}O\left(\frac{k^4}{n^2}\right)=O\left(\frac{1}{n^2}\right)$$ ? – Norbert Jun 28 '12 at 20:33
@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)$$ ! – robjohn Jun 28 '12 at 21:06
Thakns, I'll try to learn $O$-approach in future. – Norbert Jun 28 '12 at 21:07
I 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<k\le d(n)$ and $k>d(n)$, where $d(n)\prec n$. PS: $f(n)\prec g(n)\iff\lim_{n\to\infty}f(n)/g(n)=0$. – Frank Science Jun 29 '12 at 1:39
Good approximation, where $\Theta_n(t)$ is not needed. – Frank Science Jun 29 '12 at 1:42

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

-
You 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<n$ and then to invoke the Monotone Convergence Theorem. – Benji Jun 28 '12 at 10:09
You could just use the sequence version of the Monotone Convergence Theorem. – Benji Jun 28 '12 at 10:59
Thanks, I didn't knew that – Norbert Jun 28 '12 at 11:02
Could you compute the asymptotics, not just the limits. I'm very interested in such theory. – Frank Science Jun 28 '12 at 11:52
@FrankScience Why don't you use Euler–Maclaurin formula? – Norbert Jun 28 '12 at 14:52

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.

-
I 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.$$ – Siminore Jun 28 '12 at 8:58
Sorry: the limit should be 1, in the previous comment. – Siminore Jun 28 '12 at 9:22
@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 – mixedmath Jun 28 '12 at 16:05
Yes, it's a matter of passing to the limit inside a series. – Siminore Jun 28 '12 at 16:44

$\sum_{k=1}^n(k/n)^n=\sum_{0<k\le n}(1-k/n)^n$, and let $a_k(n)=(1-k/n)^n$. For $0<k\le n^{1/3}$, we have $$\ln a_k(n)=n\ln\left(1-\frac kn\right)=-n\left(\frac kn+O\left(\frac kn\right)\right)=-k+O\left(\frac{k^2}n\right)$$ thus $$a_k(n)=e^{-k}\left(1+O\left(\frac{k^2}n\right)\right)$$ Let $b_k(n)=e^{-k}$, $c_k(n)=k^2e^{-k}/n$, we have $a_k(n)=b_k(n)+O(c_k(n))$ over $0<k\le n^{1/3}$. Thus, we have $$\sum_{0<k\le n}a_k(n)=\sum_{k>0}b_k(n)+O(\Sigma_a(n))+O(\Sigma_b(n))+O(\Sigma_c(n))$$ where $$\sum_{k>0}b_k(n)=\sum_{k>0}e^{-k}=\frac e{e-1}$$ and \begin{align*} \Sigma_b(n)&=\sum_{k>n^{1/3}}e^{-k}=O(e^{n^{1/3}})\\ \Sigma_a(n)&=\sum_{n^{1/3}<k\le n}\left(1-\frac kn\right)^n\le\sum_{n^{1/3}<k\le n}e^{-k}=O(e^{n^{1/3}})\\ \Sigma_c(n)&=\sum_{0<k\le n^{1/3}}e^{-k}k^2/n\le\sum_{k>0}e^{-k}k^2/n=O\left(\frac 1n\right) \end{align*} Hence, we have $\sum_{0<k\le n}(1-k/n)^n=e/(e-1)+O(1/n)$.

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!

-
In my answer, I show how to get more accuracy by including more terms in in the series for $\log$ and $\exp$. – robjohn Jun 28 '12 at 18:06
@robjohn Thanks. – Frank Science Jun 29 '12 at 1:36