Asintótica comportamiento de sumas de potencias consecutivas

Question

Deje $S_k(n)$$k = 0, 1, 2, \ldots$, se define como sigue

$$S_k(n) = \sum_{i=1}^n \ i^k$$

Fijo (pequeño) $k$, se puede determinar una buena fórmula en términos de$n$, que se puede demostrar utilizando, por ejemplo, la inducción. Para las pequeñas $k$ nosotros por ejemplo obtener

$$\begin{align} S_0(n) &= n\\ S_1(n) &= \frac{1}{2}n^2 + \frac{1}{2}n \\ S_2(n) &= \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n \\ S_3(n) &= \frac{1}{4}n^4 + \frac{1}{2}n^3 + \frac{1}{4}n^2 \\ S_4(n) &= \frac{1}{5}n^5 + \frac{1}{2}n^4 + \frac{1}{3}n^3 - \frac{1}{30}n \end{align}$$

Los coeficientes de estos polinomios son relacionados a la de Bernoulli-números, y llegar arbitrario con coeficientes en estos polinomios (es decir, el coeficiente de $n^m$ $S_k(n)$ grandes $k,m$) no es tan fácil. Sin embargo, th dos primeros coeficientes siguen un patrón simple: el coeficiente de $n^{k+1}$ $\frac{1}{k+1}$ y el coeficiente de $n^k$ ( $k > 0$ ) siempre es $\frac{1}{2}$. Mi principal pregunta es ahora:

¿Cómo podemos demostrar que $S_k(n) = \frac{1}{k+1}n^{k+1} + \frac{1}{2}n^k + O(n^{k-1})$$k > 0$?

El primer coeficiente puede ser explicado de manera intuitiva, como

$$S_k(n) = \sum_{i=1}^n \ i^k \approx \int_{i=1}^n i^k di \approx \frac{n^{k+1}}{k+1}$$

Tal vez usted podría hacer esto más rigurosas, pero no veo cómo va a llegar el plazo $\frac{1}{2}n^k$ con este.

También, mientras que el coeficiente de $n^{k+1}$ puede ser explicado de manera intuitiva, no es claro para mí por qué el coeficiente de $n^k$$\frac{1}{2}$, y por qué este es fijo, mientras que por ejemplo, el coeficiente de $n^{k-1}$ es diferente para los diferentes $k$. Si alguien podría explicar que, que se agradece también.

Gracias.

Answer 1

Este es un clásico de la aplicación de la de Euler-Maclaurin fórmula para aproximar una suma por una integral. De Euler-Maclaurin dice

$$\sum_{i=0}^n f(i) = \int_0^n f(x) dx + \frac{f(n)+f(0)}{2} + \sum_{i=1}^{\infty} \frac{B_{2i}}{(2i)!} \left(f^{(2i-1)}(n)-f^{(2i-1)}(0)\right),$$ donde $B_i$ $i$th número de Bernoulli.

Si tomamos $f(x) = x^k$, la serie infinita es en realidad finita. Los dos primeros términos más los dos primeros términos de la serie nos dan, para $k \geq 2$, $$\sum_{i=0}^n i^k = \int_0^n x^k dx + \frac{n^k}{2} + \frac{B_2}{2}k n^{k-1} + O(n^{k-3}) = \frac{n^{k+1}}{k+1} + \frac{n^k}{2} + \frac{k n^{k-1}}{12} + O(n^{k-3}),$$ que es lo que estamos pidiendo.

Y, por supuesto, si quieres una mejor aproximación asintótica usted puede simplemente tomar más términos de la serie.

Esto también explica por qué la $n^k$ plazo es el único cuyo coeficiente no cambia; es el único en la fórmula en la que la función de $f(x) = x^k$ más que su integral o uno de sus derivados está siendo evaluada en la $n$.

Answer 2

La manera estándar de suma $\sum\limits_{r=1}^n r^k$ recibe esta estimación. Tenemos: $$ (r+1)^{k+1} - r^{k+1} = (k+1) r^{k} + \frac{k(k+1)}{2} r^{k-1} + O(r^{k-2}). $$ Sumando esta ecuación para $r = 0, 1, 2, \ldots, n$, obtenemos: $$ (n+1)^{k+1} + O(1) = (k+1) \sum_{i=0}^nr^{k} + \frac{k(k+1)}{2} \sum_{i=0}^n r^{k-1} + \sum_{i=0}^nO(r^{k-2}). $$ Utilizando el inductivo hipótesis de que la $\sum_{r=0}^n r^j = \frac{n^{j+1}}{j+1} + \frac{n^j}{2}$ para $j < k$, obtenemos: $$ \begin{eqnarray*} (k+1) \sum_{r=0}^nr^{k} &=& (n+1)^{k+1} + O(1) - \frac{k(k+1)}{2} \left(\frac{n^k}{k} + \frac{n^{k-1}}{2} \right)+ \sum_{r=0}^nO(r^{k-2}). \\ &\stackrel{(1)}{=}& \left[ n^{k+1} + (k+1)n^{k} + O(n^{k-1}) \right] + O(1) - \frac{(k+1)n^k}{2} + O(n^{k-1})+ O(r^{k-1}) \\ &=& n^{k+1} + \frac{k+1}{2} n^k + O(n^{k-1}), \end{eqnarray*} $$ donde $(1)$ se sigue del teorema del binomio. Esto es equivalente a la demanda.