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

Suppose $n\in\mathbb{Z}$ and $n > 0$. Let $$H_n = 1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1.$$

I would like to find a Big O bound for $H_n$. A Big $\Theta$ result would be even better.

Solution 1:

Let $0<a<b<1$. For every $an\leqslant k\leqslant bn$, $k^{-k+n+1}\geqslant(an)^{(1-b)n}$ hence $H_n\geqslant(b-a)n(an)^{(1-b)n}$. Thus $\log (H_n)\geqslant (1-b)n\log(n)+(1-b)n\log(a)+\log(b-a)$, which proves that $$ \liminf\limits_{n\to\infty}\log(H_n)/(n\log(n))\geqslant1-b. $$ On the other hand, $$ H_{n+1}=n+1+\sum\limits_{k=1}^nk^{n+2-k}\leqslant n+1+n\sum\limits_{k=1}^nk^{n+1-k}=n+1+nH_n. $$ Hence, as @J.J. noted in a comment, if $H_n<n!$ then $$H_{n+1}<n+1+n\cdot n!\leqslant(n+1)!$$ if $n+1\leqslant n!$, that is, if $n\geqslant3$. Since $H_3=8>3!$ but $H_4=22<4!$, this proves that $H_n<n!$ for every $n\geqslant4$. Thus, $$ \color{red}{\lim\limits_{n\to\infty}\log(H_n)/(n\log n)=1}, $$ which may be rewritten as $H_n=n^{n+o(n)}$. To go further, rewrite the inequality between $H_n$ and $H_{n+1}$ written above as $$ \frac{H_{n+1}}{n!}\leqslant\frac{n+1}{n!}+\frac{H_n}{(n-1)!}, $$ which, since $H_1=1$, shows that $H_{n}<(2\mathrm e)(n-1)!$ for every $n\geqslant1$.

Be aware though, that this is not the end of the story yet since, for every positive integer $k$, there exists a finite constant $c_k$ such that $H_n<c_k(n-k)!$ for every $n\geqslant k$... hence $$ \color{blue}{H_n=n^{n-\alpha(n)}}, $$ with $\alpha(n)\to+\infty$ and $\alpha(n)/n\to0$ when $n\to\infty$.

Solution 2:

My approach is very much along the same line as that of leonbloy.

Let $f(k) = k^{n+1-k}$. Use Euler-Maclaurin formula:

$$ \begin{eqnarray} \sum_{k=1}^n f(k) &=& \int_1^n f(x) \mathrm{d} x + \frac{1}{2} \left( f(1) + f(n) \right) + \sum_{m=1}^q \frac{B_{2m}}{(2m)!} \left( f^{(2m-1)}(n) - f^{(2m-1)}(1) \right) \\ &&+ \frac{1}{(2q)!} \int_1^n B_{2q}(\{t\}) f^{(2q)}(t) \mathrm{d} t \end{eqnarray} $$ Since $f(1) = 1$ and $f(n)=n$. Asymptotically, $f^{(2m-1)}(1) \sim -n \cdot \log^{2m-1}(n)$ and $f^{(2m-1)}(n) \sim n^{2m-1}$.

Thus the main term comes from the integral. Let $x=1+(n-1)t$. $$ \int_1^n x^{n+1-x} \mathrm{d} x = (n-1) \int_0^1 \left( 1 + (n-1) t \right)^{t+n(1-t)} \,\, \mathrm{d} t $$ The integrand is sharp-peaked with peak location at $$ t_0 = \frac{1}{n-1} \left( \frac{n+1}{W((n+1) \, \mathrm{e})} -1 \right) $$ Logarithm of the integrand, expanded in the vicinity of $t_0$: $$ \left( n + t - n t \right) \log\left(1 + (n-1) t \right) = (n+1) \left( w_n + \frac{1}{w_n} - 2 \right) - \frac{\sigma_n}{2} ( t-t_0)^2 + o((t-t_0)^2) $$ where $w_n = W((n+1)\mathrm{e})$ and $\sigma_n = \frac{(n-1)^2 w_n ( w_n + 1)}{n+1}$.

Thus $$ \sum_{k=1}^n k^{n+1-k} \sim \exp\left( (n+1) \left( w_n + \frac{1}{w_n} - 2 \right) \right) \sqrt{\frac{2\pi (n+1)}{w_n (1+w_n)}} $$

Here is the numerical simulation, showing the agreement on logarithmic scale: