Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Please start accepting answers to your earlier questions. In Math.SE, this is considered important feedback for answerers. You can accept an answer by clicking the green tick/check mark under it. –  Srivatsan Nov 10 '11 at 23:56

5 Answers 5

up vote 25 down vote accepted

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

share|improve this answer
    
A neat argument with a simple estimate! Of course, +1 upvote. Were you already aware of how $H_{n}$ will behave? –  sos440 Mar 21 at 4:50
    
@sos440 Thanks. I was not. –  Did Mar 21 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

share|improve this answer

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.

share|improve this answer
3  
You can also show quite easily by induction that $H_n < n!$ when $n \ge 4$. –  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-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
share|improve this answer
    
I was just thinking of this approach, when I scrolled down and saw your answer. –  robjohn Nov 2 '11 at 15:08
    
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.) –  Did Nov 2 '11 at 15:43
    
I typed [sum k^(31-k) from k=1 to 30] in W|A and got 3939676100069476203757, whose logarithm is 49.7253854647... –  Did Nov 2 '11 at 15:48
    
@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. –  leonbloy Nov 2 '11 at 15:49
    
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.) –  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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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