# Can I get better approximation of $\sum_{k=1}^{n} k^k$

Is it possible to get approximation$f(n)$ of $\sum_{k=1}^{n} k^k$ with \begin{align} \lim_{n\to +\infty }\left(f(n)-\sum_{k=1}^{n} k^k\right)=0 \end{align} Thanks for your attention!

-
$\sum_{k=1}nn^n=n\cdot n^n=n^{n+1}$; is that really what you intended? –  Brian M. Scott Sep 8 '12 at 1:46
You mean $$\sum_{k=1}^{n} k^k$$ right? –  Pedro Tamaroff Sep 8 '12 at 1:46
@Peter: I don’t think that it’s appropriate to change the substance of a question without the OP’s input. –  Brian M. Scott Sep 8 '12 at 1:49
@BrianM.Scott Oh, well. –  Pedro Tamaroff Sep 8 '12 at 1:56
@PeterTamaroff Yeah,Sorry for my mistake –  Golbez Sep 8 '12 at 2:24

I have no idea how $f(n)$ should look like, and actually I suspect that there is no such simple formula for $f(n)$. But at least we can improve Sasha's asymptotics. Indeed, a moment of thought gives that for any fixed $m$, we have

\begin{align*} \frac{1}{n^n} \sum_{k=1}^{n} k^k &= \sum_{k=0}^{n-1} \left(1 - \frac{k}{n}\right)^{n-k}\frac{1}{n^k} \\ &= \sum_{k=0}^{n-1} \frac{1}{(en)^k}\exp\bigg\{k \sum_{j=1}^{\infty} \frac{(k/n)^j}{j(j+1)} \bigg\} \\ &= \sum_{k=0}^{m} \frac{1}{(en)^k}\exp\bigg\{k \sum_{j=1}^{m-k} \frac{(k/n)^j}{j(j+1)} \bigg\} + \mathcal{O}(n^{-(m+1)}) \end{align*}

Plugging $m = 1$, we have

$$\frac{1}{n^n} \sum_{k=1}^{n} k^k = 1 + \frac{1}{en} + \mathcal{O}(n^{-2})$$

With aid of Mathematica, for $m = 4$ we have

\begin{align*} \frac{1}{n^n} \sum_{k=1}^{n} k^k &= 1 + \frac{1}{en} + \left( \frac{1}{e^2}+\frac{1}{2e}\right) \frac{1}{n^2} + \left(\frac{1}{e^3}+\frac{2}{e^2}+\frac{7}{24 e}\right)\frac{1}{n^3} \\ &\qquad + \left(\frac{1}{e^4}+\frac{9}{2e^3}+\frac{10}{3 e^2}+\frac{3}{16 e}\right)\frac{1}{n^4} + \mathcal{O}(n^{-5}) \end{align*}

-