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!
Can I get better approximation of $\sum_{k=1}^{n} k^k$
-
1$\sum_{k=1}nn^n=n\cdot n^n=n^{n+1}$; is that really what you intended? – 2012-09-08
-
0You mean $$\sum_{k=1}^{n} k^k$$ right? – 2012-09-08
-
2@Peter: I don’t think that it’s appropriate to change the substance of a question without the OP’s input. – 2012-09-08
-
0@BrianM.Scott Oh, well. – 2012-09-08
-
0@PeterTamaroff Yeah,Sorry for my mistake – 2012-09-08
-
0Notice that $$ \sum_{k=1}^{n} k^k \leqslant \sum_{k=1}^{n} n^k = \frac{n^n-1}{n-1} n $$ Thus the limit $$ \lim\limits_{n\to\infty} n^{-n} \sum\limits_{k=1}^{n} k^k = 1 $$ – 2012-09-08
-
0@Sasha I know, but what i need is $\lim_{n\to \infty }\left(f(n)-\sum_{k=1}^{n} k^k\right)=0$, thanks for your reply – 2012-09-08
-
0It would be very surprising if there were such a function $f(n)$ with a closed-form expression. – 2012-09-08
1 Answers
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*}