Asintótica de $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$

Question

Supongamos que $n\in\mathbb{Z}$ y $n > 0$ . Sea $$H_n = 1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1.$$

Me gustaría encontrar un Big O destinado a $H_n$ . Un gran $\Theta$ resultado sería aún mejor.

Answer 1

Dejemos que $0<a<b<1$ . Para cada $an\leqslant k\leqslant bn$ , $k^{-k+n+1}\geqslant(an)^{(1-b)n}$ por lo que $H_n\geqslant(b-a)n(an)^{(1-b)n}$ . Así, $\log (H_n)\geqslant (1-b)n\log(n)+(1-b)n\log(a)+\log(b-a)$ lo que demuestra que $$ \liminf\limits_{n\to\infty}\log(H_n)/(n\log(n))\geqslant1-b. $$ Por otro lado, $$ 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. $$ Por lo tanto, como señaló @J.J. en un comentario, si $H_n<n!$ entonces $$H_{n+1}<n+1+n\cdot n!\leqslant(n+1)!$$ si $n+1\leqslant n!$ es decir, si $n\geqslant3$ . Desde $H_3=8>3!$ pero $H_4=22<4!$ Esto demuestra que $H_n<n!$ por cada $n\geqslant4$ . Así, $$ \color{red}{\lim\limits_{n\to\infty}\log(H_n)/(n\log n)=1}, $$ que puede reescribirse como $H_n=n^{n+o(n)}$ . Para ir más allá, reescribe la desigualdad entre $H_n$ y $H_{n+1}$ escrito arriba como $$ \frac{H_{n+1}}{n!}\leqslant\frac{n+1}{n!}+\frac{H_n}{(n-1)!}, $$ que, desde $H_1=1$ , muestra que $H_{n}<(2\mathrm e)(n-1)!$ por cada $n\geqslant1$ .

Sin embargo, hay que tener en cuenta que este no es el final de la historia ya que, para cada número entero positivo $k$ existe una constante finita $c_k$ tal que $H_n<c_k(n-k)!$ por cada $n\geqslant k$ ... por lo tanto $$ \color{blue}{H_n=n^{n-\alpha(n)}}, $$ con $\alpha(n)\to+\infty$ y $\alpha(n)/n\to0$ cuando $n\to\infty$ .

Answer 2

Mi enfoque es muy parecido al de que de leonbloy .

Dejemos que $f(k) = k^{n+1-k}$ . Utilice la fórmula de Euler-Maclaurin:

$$ \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} $$ Desde $f(1) = 1$ y $f(n)=n$ . Asintóticamente, $f^{(2m-1)}(1) \sim -n \cdot \log^{2m-1}(n)$ y $f^{(2m-1)}(n) \sim n^{2m-1}$ .

Así, el término principal proviene de la integral. Sea $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 $$ El integrando tiene un pico agudo con la ubicación del pico en $$ t_0 = \frac{1}{n-1} \left( \frac{n+1}{W((n+1) \, \mathrm{e})} -1 \right) $$ Logaritmo del integrando, expandido en las proximidades de $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) $$ donde $w_n = W((n+1)\mathrm{e})$ y $\sigma_n = \frac{(n-1)^2 w_n ( w_n + 1)}{n+1}$ .

Así, $$ \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)}} $$

Aquí está la simulación numérica, que muestra la concordancia en la escala logarítmica:

Answer 3

Otra idea, aproximándose a una integral y utilizando Laplace

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

Dejemos que $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)$$

El máximo global de $g(x)$ se alcanza (tras algunas manipulaciones) en $$x_0(m)=\frac{m}{W( e \; m)} \approx \frac{m}{1+ \log m - \log (1 +\log m)}$$

donde $W(\cdot)$ es la función de Lambert (la última aproximación asintótica es para tener una idea del orden, pero puede/debe ser refinada ver aquí - todas las asintóticas son complicadas aquí).

Ahora, aproximamos la integral por el método de Laplace:

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

O

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

Un poco de código Maxima

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;

Este enfoque puede ser especialmente útil para calcular numéricamente la suma para grandes valores de $N$ . Por ejemplo, algunos valores de $log(H_n)$

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

Answer 4

Un límite bastante trivial es

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

Sin embargo, no he encontrado un vínculo estrecho. También para los interesados, se sabe que esta secuencia OEIS .

Answer 5

He aquí una idea sencilla que puede o no llevar a alguna parte.

Tenga en cuenta que $(k+1)^{n-k-1} \geq k^{n-k}$ si y sólo si

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

Para $k \leq \sqrt{n-1}$ por Bernoulli

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

Así obtenemos el siguiente resultado:

Lema : La secuencia $k^{n-k}$ es creciente para todos los $k \leq \sqrt{n-1}$ .

Ahora bien, si $k > \sqrt{n-1}$ y $n$ grande, tenemos la siguiente aproximación:

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

La desigualdad $e^{\frac{n-1}{k}-1} < k$ es cierto para todos los $k > k_0(n)$ . Desgraciadamente no puedo calcular un buen presupuesto para $k_0(n)$ Es fácil obtener una estimación aproximada.

De todos modos, esto demuestra que con seguridad $k^{n-k}$ en pliegues hasta $k=\sqrt{n-1}$ y disminuye para todos $k \geq k_0(n)$ . Un buen cálculo de $k_0$ debería conducir a una estimación decente pero no muy buena.