3
$\begingroup$

Possible Duplicate:
Asymptotics of $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$

About how big is is the sum $\sum_{k=0}^n k^{n-k}$? At the least, can we get an upper bound on it that isn't terrible? (I would consider $(n+1)n^n$, or anything not significantly smaller than it, to be terrible.)

  • 0
    FWIW, http://oeis.org/A0268982011-12-01
  • 0
    [Wolfram Alpha](http://www.wolframalpha.com/input/?i=maximize+x%5E%2820-x%29+from+x%3D0+to+x%3D20) says that the maximum of $x^{n-x}$ ocurrs at $x = e^{W(n e)-1}$ and so an upper bound for the sum is $(n+1) \exp(e^{W(n e)-1}+n W(n e)-2n)$ but this is not tight.2011-12-01
  • 3
    Related: http://math.stackexchange.com/questions/77790/asymptotics-of-1n-2n-1-3n-2-cdots-n-12-n12011-12-01
  • 3
    @Zev, it's the same question. The sum here is $1 + H_{n-1}$, to use the notation there.2011-12-01
  • 0
    @Yuval: Ah, I was thrown by the different indexing :)2011-12-01
  • 0
    Oops, completely missed that. Sorry, I'll delete this! Edit: Once it lets me...2011-12-01
  • 0
    @Harry: Don't worry, happens to everyone! And I don't think that deletion is necessary; someone might search for your formulation, and we'd want them to find the same info. This is also the general opinion [on this meta.SO post](http://meta.stackexchange.com/questions/32311/do-not-delete-duplicates).2011-12-01

0 Answers 0