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.


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

  • $\begingroup$ A neat argument with a simple estimate! Of course, +1 upvote. Were you already aware of how $H_{n}$ will behave? $\endgroup$ – Sangchul Lee Mar 21 '14 at 4:50
  • $\begingroup$ @sos440 Thanks. I was not. $\endgroup$ – Did Mar 21 '14 at 6:56

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:

enter image description here


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.

  • 3
    $\begingroup$ You can also show quite easily by induction that $H_n < n!$ when $n \ge 4$. $\endgroup$ – J. J. Nov 1 '11 at 17:28

Another idea, aproximating to an integral and using Laplace

$$H_n=\sum_{k=1}^{n} k^{n+1-k} \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}}$$


$$\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

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
  • $\begingroup$ I was just thinking of this approach, when I scrolled down and saw your answer. $\endgroup$ – robjohn Nov 2 '11 at 15:08
  • $\begingroup$ Interesting approach, which begs for some clarifications. (1) The use of the Laplace method seems rather unorthodox since $g$ depends on $m$. (2) You mention some tricky asymptotics and a second approximation, but what these are is rather mysterious. (3) As is the method used to compute the approx values. (Note that the captions exact and approx might have been exchanged.) $\endgroup$ – Did Nov 2 '11 at 15:43
  • $\begingroup$ I typed [sum k^(31-k) from k=1 to 30] in W|A and got 3939676100069476203757, whose logarithm is 49.7253854647... $\endgroup$ – Did Nov 2 '11 at 15:48
  • $\begingroup$ @DidierPiau: 1) that's totally right 2) partially edited 3) i had mixed the columns for some rows (yikes), fixed, and maxima code polished. In case of doubt: the 'exact' column is just the original sum, the other is my 'best' approximation, ap2l(N) in maxima. $\endgroup$ – leonbloy Nov 2 '11 at 15:49
  • $\begingroup$ Mmmm... Some things disappeared from your post but not the mysteries. To me, the main one is still this pseudo-Laplace method applied to a function depending on $n$. But the numerical accuracy is striking... (Side note: $O(1)$ is wrong.) $\endgroup$ – Did Nov 2 '11 at 16:04

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.