3
$\begingroup$

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!

  • 1
    $\sum_{k=1}nn^n=n\cdot n^n=n^{n+1}$; is that really what you intended?2012-09-08
  • 0
    You 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 mistake2012-09-08
  • 0
    Notice 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 reply2012-09-08
  • 0
    It would be very surprising if there were such a function $f(n)$ with a closed-form expression.2012-09-08

1 Answers 1

3

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