Sum of the First n Natural Numbers Power n

Question

How would I estimate the sum of a series of numbers like this: $$1^n+2^n+\cdots+n^n$$

Answer 1

The sequence $$S_n=\sum_{k=1}^n k^n=H_n^{(-n)}$$ where appear generalized harmonic numbers.

If you look here, you will find that the asymptotics is given by $$S_n \sim \frac{e }{e-1}n^n$$ Rigorous is $$S_n=\zeta (-n)-\zeta (-n,n+1)$$ where appear the Riemann zeta function and the generalized Riemann zeta function.

Edit

Without any proof, it seems that a good approximation could be $$\color{blue}{S_n\sim\frac{ (e n+1)}{(e-1) (n+1)}n^n}$$ The table below compares the results for the first values of $n$. $$\left( \begin{array}{ccc} n & \sum_{k=1}^n k^n & \text{Round}\left[\frac{ (e n+1)}{(e-1) (n+1)}n^n\right] \\ 1 & 1 & 1 \\ 2 & 5 & 5 \\ 3 & 36 & 36 \\ 4 & 354 & 354 \\ 5 & 4423 & 4425 \\ 6 & 67144 & 67171 \\ 7 & 1199883 & 1200304 \\ 8 & 24677030 & 24684612 \\ 9 & 574148140 & 574304985 \\ 10 & 14910676160 & 14914341925 \\ 11 & 427580444554 & 427675990236 \\ 12 & 13419209344613 & 13421957361110 \\ 13 & 457507427534348 & 457593884876401 \\ 14 & 16838135509568547 & 16841089312342855 \\ 15 & 665369566514106019 & 665478473553144000 \\ 16 & 28097216849617149638 & 28101527071305611528 \\ 17 & 1262717032961647490451 & 1262899292504270591313 \\ 18 & 60174237491183944648348 & 60182438244917445266889 \\ 19 & 3030892828884033952381378 & 3031284048960901518840700 \\ 20 & 160889061690602034858545167 & 160908785696531607621474266 \end{array} \right)$$

For $n=20$, the result is off by $0.0126$% and for $n=100$, the result is off by $0.0024$%.

For sure, this leads to the same asymptotics as the one mentioned in the $OEIS$ page.

Answer 2

We have $$ 1^n + \cdots + n^n = n^n\left(\left(\frac{1}{n}\right)^n + \left(\frac{2}{n}\right)^n + \cdots + \left(\frac{n-1}{n}\right)^n + \left(\frac{n}{n}\right)^n\right) $$ Now, we use the approximation $\left(\frac{n-k}{n}\right)^n\approx e^{-k}$. It will be quite accurate for the rightmost terms, and the leftmost terms are small anyway, so the error in approximation there doesn't matter much. Thus we continue $$ \approx n^n\left(e^{1-n} + e^{2-n} + \cdots + e^{-1} + e^0\right)\\ = n^n\frac{e^{1-n}(1-e^n)}{1-e} $$ According to WolframAlpha, it's off by $3\%$ for $n = 20$, and $0.7\%$ for $n = 100$. I know that one shouldn't extrapolate, but that looks like a pretty decent approximation to me.

Answer 3

If you were to integrate $x^n$ after the first couple of terms, you could have

$\frac{1 + 2^n + [(n + 0.5)^{n + 1} - (2.5)^{n + 1}]}{(n + 1)}$ for an approximation.