Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
How could you show that the limit exist? –  B. S. Jun 28 '12 at 8:25
1  
@Siminore: The sum is very similar to $\int_{0}^{1}x^xdx$. Isn't it? –  B. 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
add comment

4 Answers 4

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

share|improve this answer
    
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
show 9 more comments

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

share|improve this answer
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. –  bobobinks Jun 28 '12 at 10:09
    
You could just use the sequence version of the Monotone Convergence Theorem. –  bobobinks 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
show 1 more comment

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.

share|improve this answer
    
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
add comment

$\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!

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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