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?
 A: 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.
A: $\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!
A: 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$.
A: 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}}. $$
A: First, we can rewrite the formula:
$$\frac{\sum_{i=1}^{n}i^n}{n^n} = \sum_{i=1}^{n}\frac{i^n}{n^n} = \sum_{i=0}^{n-1}\frac{(n-i)^n}{n^n} = \sum_{i=0}^{n-1}\left(1-\frac{i}{n} \right)^n$$
We can easily prove the following inequality relations:
$$\frac{1}{\text{e}^i} - \frac{i^2}{n\text{e}^i} \le \frac{1}{\text{e}^i}\left(1-\frac{i}{n} \right)^i\le \left(1-\frac{i}{n} \right)^n \le \frac{1}{\text{e}^i} $$
Therefore, we can get
$$\sum_{i=0}^{n-1}\frac{1}{\text{e}^i}-\frac{1}{n}\sum_{i=0}^{n-1}\frac{i^2}{\text{e}^i}\le\sum_{i=0}^{n-1}\left(1-\frac{i}{n}  \right)^n \le \sum_{i=0}^{n-1}\frac{1}{\text{e}^i}$$
So
$$\lim_{n\to \infty}\sum_{i=0}^{n-1}\frac{1}{\text{e}^i}-\lim_{n\to \infty}\frac{1}{n}\sum_{i=0}^{n-1}\frac{i^2}{\text{e}^i}\le\lim_{n\to \infty}\sum_{i=0}^{n-1}\left(1-\frac{i}{n} \right)^n \le \lim_{n\to \infty}\sum_{i=0}^{n-1}\frac{1}{\text{e}^i}$$
We can easily know that
$$\lim_{n\to \infty}\sum_{i=0}^{n-1}\frac{1}{\text{e}^i} = \frac{\text{e}}{\text{e}-1}$$
$$\lim_{n\to \infty}\frac{1}{n}\sum_{i=0}^{n-1}\frac{i^2}{\text{e}^i} = \left(\lim_{n\to \infty}\frac{1}{n}\right)\cdot \left(\lim_{n\to \infty}\sum_{i=0}^{n-1}\frac{i^2}{\text{e}^i}\right) = 0 \cdot \frac{\text{e}(\text{e}+1)}{(\text{e}-1)^3} = 0$$
Finally, we can get the answer:
$$\lim_{n\to \infty} \frac{\sum_{i=1}^{n}i^n}{n^n} = \lim_{n\to \infty}\sum_{i=0}^{n-1}\left(1-\frac{i}{n}  \right)^n = \frac{\text{e}}{\text{e}-1}$$
For more details, you can watch my video on Bilibili, if you have learned Chinese.
Here is my video link: https://www.bilibili.com/video/BV1yG411g7K1/
A: 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}}
$$
