20
$\begingroup$

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.

5 Answers 5

25

Let $0. 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 then $H_{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 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 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$.

  • 0
    @sos440 Thanks. I was not.2014-03-21
7

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

5

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
    You can also show quite easily by induction that H_n < n! when $n \ge 4$.2011-11-01
5

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

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 
  • 0
    @DidierPiau well, not m$y$ day... removed that stupid O(1), thanks2011-11-02
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.