por qué es $\sum\limits_{k=1}^{n} k^m$ un polinomio de grado $m+1$ en $n$

Question

Por qué es $\sum\limits_{k=1}^{n} k^m$ un polinomio de grado $m+1$ en $n$ ?

Sé que esto es bien conocido. Pero, ¿cómo demostrarlo con rigor? Ni siquiera la inducción matemática parece tan sencilla.

Gracias.

Answer 1

Dejemos que $V$ sea el espacio de todos los polinomios $f : \mathbb{N}_{\ge 0} \to F$ (donde $F$ es un campo de característica cero). Definir el operador de diferencia hacia adelante $\Delta f(n) = f(n+1) - f(n)$ . No es difícil ver que la diferencia hacia delante de un polinomio de grado $d$ es un polinomio de grado $d-1$ por lo que se define un operador lineal $V_d \to V_{d-1}$ donde $V_d$ es el espacio de los polinomios de grado máximo $d$ . Tenga en cuenta que $\dim V_d = d+1$ .

Queremos pensar en $\Delta$ como un análogo discreto de la derivada, por lo que es natural definir el correspondiente análogo discreto de la integral $(\int f)(n) = \sum_{k=0}^{n-1} f(k)$ . Pero, por supuesto, tenemos que demostrar que esto realmente envía polinomios a polinomios. Dado que $(\int \Delta f)(n) = f(n) - f(0)$ (el "teorema fundamental del cálculo discreto"), basta con demostrar que la diferencia hacia delante es suryente como operador lineal $V_d \to V_{d-1}$ .

Pero por el "teorema fundamental", la imagen de la integral es precisamente el subespacio de $V_d$ de polinomios tales que $f(0) = 0$ por lo que la diferencia e integral hacia adelante definen un isomorfismo entre $V_{d-1}$ y este subespacio.

Más explícitamente, se puede observar que $\Delta$ es triangular superior en la base estándar, trabajar por inducción, o utilizar la Base de Newton $1, n, {n \choose 2}, {n \choose 3}, ...$ para el espacio de los polinomios. En esta base tenemos $\Delta {n \choose k} = {n \choose k-1}$ y ahora el resultado es realmente obvio.

El método de las diferencias finitas proporciona una forma bastante limpia de derivar una fórmula para $\sum n^m$ por el hecho de ser fijo $m$ . De hecho, para cualquier polinomio $f(n)$ tenemos la "fórmula discreta de Taylor"

$$f(n) = \sum_{k \ge 0} \Delta^k f(0) {n \choose k}$$

y es fácil calcular los números $\Delta^k f(0)$ mediante una tabla de diferencias finitas y, a continuación, sustituir ${n \choose k}$ por ${n \choose k+1}$ . Escribí una entrada en el blog que explica esto, pero cada vez es más difícil de encontrar; también lo expliqué en mi notas sobre las funciones generadoras .

Answer 2

Se puede establecer una fórmula recursiva para $\sum_{k=0}^n k^m $ al señalar que

$$(n+1)^{m+1} = \sum_{k=0}^n (k+1)^{m+1}- \sum_{k=0}^n k^{m+1}$$ $$ = { m+1 \choose 1} \sum_{k=0}^n k^m + { m+1 \choose 2} \sum_{k=0}^n k^{m-1} + \cdots $$

expandiendo la primera suma en el lado derecho por el teorema del binomio. A continuación, desplaza todos los demás sumandos, excepto $\sum_{k=0}^n k^m $ al LHS.

Así que obtenemos

$${ m+1 \choose 1} \sum_{k=0}^n k^m = (n+1)^{m+1} - { m+1 \choose 2} \sum_{k=0}^n k^{m-1} - { m+1 \choose 3} \sum_{k=0}^n k^{m-2} + \cdots $$

Answer 3

La fórmula se cae directamente si usamos el Fórmula de suma de Euler Maclaurin.

Para $\displaystyle f(x) = x^m$ tenemos

$$ \sum_{k=0}^{n} f(k) = \int_{0}^{n} f(x)\ \text{d}x + \frac{n^m}{2} + \sum_{j=0}^{\infty} \frac{B_{2j}}{(2j)!} (f^{(2j-1)}(n) - f^{(2j-1)}(0))$$

Donde $\displaystyle B_j$ son los números de Bernoulli y $\displaystyle f^{(j)}(x)$ es el $\displaystyle j^{th}$ derivado de $\displaystyle f$ .

Desde $\displaystyle f(x)$ es polinómica, los términos en

$$ \sum_{j=0}^{\infty} \frac{B_{2j}}{(2j)!} (f^{(2j-1)}(n) - f^{(2j-1)}(0))$$

todos son cero después de un punto ( $\displaystyle 2j-1 \gt m$ ) y así obtenemos la fórmula de

$\displaystyle \sum_{k=0}^{m} k^m$ como un polinomio en $\displaystyle n$ , con grado $m+1$ .

Answer 4

La respuesta de Qiaochu es (como siempre ) acertada.

Sólo quería mencionar que también escribí algunas notas sobre el "cálculo discreto" que toma la cuestión de encontrar una forma cerrada para las sumas de $k$ a los poderes como punto de partida. Esto viene de un curso de segundo año de licenciatura que impartí sobre introducción a las pruebas, en el que hacíamos sospechosamente muchas pruebas de inducción que involucraban tales formas cerradas, y llegué a comprender tardíamente que los estudiantes las encontraban confusas. No porque no entendieran el mecanismo de la inducción (al menos, no en su mayor parte), sino porque no podían evitar fijarse en la pregunta no trivial: ¿cómo saber qué expresión de forma cerrada hay que poner en el lado derecho? En el contexto de sus ejercicios, la respuesta es: "Lo sabes porque te dan esa información como parte del problema". Pero, por supuesto, esa es una respuesta estúpida: realmente, ¿cómo sabes ?

Así que escribí estas notas sobre el tema del cálculo discreto. O, al menos, empecé a hacerlo: no están del todo completos y son un poco más complicados de lo que esperaba de los alumnos, así que acabé por no darlos. Véase especialmente la sección 2, que explora la cuestión planteada en el párrafo anterior y también da el empujoncito extra (una fórmula recursiva inocua para las sumas de potencias) que se necesita para demostrar por inducción que $1^k + \ldots + n^k$ es un grado $k+1$ polinomio en $n$ . Obsérvese también que el bonito argumento de álgebra lineal de Qiaochu viene después, en la sección 4 ("Álgebra lineal de la derivada discreta") y especialmente el teorema 11.

Como de costumbre, cualquier sugerencia o corrección sobre estas notas será bienvenida, aunque (como de costumbre) no pretendo que haya tan pocas erratas como para que merezca la pena su tiempo para señalármelas una a una.

Answer 5

Consulte La fórmula de Faulhaber