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

Question

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.

Answer 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$.

Answer 2

Another idea, aproximating to an integral and using Laplace

$$H_n=\sum_{k=1}^{n} k^{n+1-x} \approx \int_1^n x^{n+1-x} dx$$

Let $m=n+1$:

$$\int x^{m-x} dx = \int e^{m g(x)} dx \hspace{20px} , \hspace{20px} g(x)=\left(1- \frac{x}{m}\right)\log(x)$$

The global maximum of $g(x)$ is attained (after some manipulation) at $$x_0(m)=\frac{m}{W( e \; m)} \approx \frac{m}{1+ \log m - \log (1 +\log m)}$$

where $W(\cdot)$ is the Lambert function (the last asymptotic approximation is to get an idea of the order, but it can/should be refined see here - all asymptotics are tricky here.)

Now, we approximate the integral by Laplace method:

$$I(m) \approx e^{m g(x_0)} \sqrt{\frac{2 \pi}{m |g''(x_0)|}}=x_0^{m+1-x_0} \sqrt{\frac{2 \pi}{m+x_0}}$$

Or

$$\log H_n \approx (n+2-x_0) \log(x_0) + \frac{1}{2}\log{\frac{2 \pi}{n+1+x_0}}$$ with $x_0 = (n+1) /W(e \; (n+1))$

Some Maxima code

g(x,M):=(1-x/M)*log(x);
define(g1(x,M) , diff(g(x,M),x)); 
define(g2(x,M) , diff(g(x,M),x,2));
h1(M):=M/lambert_w(M * %e); 
s(M):=sum(k^(M-k), k,1, M-1);
ap1(M):= h1(M)^(M+1-h1(M)) * sqrt(2*%pi/(M+h1(M)));
ap1l(N) := (N+2-h1(N+1)) * log(h1(N+1));
ap2l(N) := ap1l(N) + log(2*%pi/(N+1+h1(N+1)))/2;

This approach might be specially useful to compute numerically the sum for large values of $N$. For example, some values of $log(H_n)$

     n             exact                 approx
    30           49.72538546           49.72496938
   100          246.40058178          246.40036689 
  1000         4271.07746405         4271.07742927

Answer 3

A rather trivial bound is

$$H_n=\sum _{k=1}^n k^{-k+n+1}\leq\sum _{k=1}^n n^{-k+n+1}=\frac{n \left(n^n-1\right)}{n-1}$$

However, I did not find a tight bound. Also for the interested ones, this sequence is known to OEIS.

Answer 4

Here is a simple idea which might or might not lead somewhere.

Note that $(k+1)^{n-k-1} \geq k^{n-k}$ if and only if

$$\left( 1+\frac{1}{k}\right)^{n-k-1} \geq k \,.$$

For $k \leq \sqrt{n-1}$, by Bernoulli

$$\left( 1+\frac{1}{k}\right)^{n-k-1} \geq 1+\frac{n-k-1}{k} =\frac{n-1}{k} \geq k \,.$$

Thus we get the following result:

Lemma: The sequence $k^{n-k}$ is increasing for all $k \leq \sqrt{n-1}$.

Now, if $k > \sqrt{n-1}$, and $n$ large, we have the following approximation:

$$\left( 1+\frac{1}{k}\right)^{n-k-1} = \left[ \left( 1+\frac{1}{k} \right)^k \right]^{\frac{n-k-1}{k}} \sim e^{\frac{n-k-1}{k}}= e^{\frac{n-1}{k}-1} $$

The inequality $e^{\frac{n-1}{k}-1} < k$ is true for all $k > k_0(n)$. Unfortunatelly I cannot figure a good estimate for $k_0(n)$, rough estimates should be easy to get.

Anyhow, this shows that for sure $k^{n-k}$ in creases up to $k=\sqrt{n-1}$ and decrease for all $k \geq k_0(n)$. A good calculation of $k_0$ should lead to a decent but not very good estimate.

Answer 5

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: