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

$$ \sum_{k=1}^n k^m = \sum_{i=0}^{m-1} T(m,i) \binom{n+i+1}{m+1}$$ donde $T(m,i)$ es un número euleriano. (OEIS id:A008292)

Desde $\binom{n+i+1}{m+1}$ es un polinomio de grado $m+1$ en $n$ Así es $ \sum_{k=1}^n k^m $ .

Answer 2

¿Nadie ha utilizado aquí la inducción mediante la suma por partes?

Definir $G_m(n) = \sum_{k=1}^n k^m$ . Demostraremos que $G_m(n)$ es un polinomio de grado $m+1$ . Sabemos que $G_1$ es un polinomio de grado $2$ con un coeficiente principal de $1/2$ . Este es el paso base.

Paso 1. Para el paso inductivo, ya que $G_1(k)-G_1(k-1)=\frac{k(k+1)}{2}-\frac{(k-1)k}{2}=k$ , suma por partes afirma que podemos escribir $G_{m+1}(n)$ como

$$\sum_{k=1}^n [G_{1}(k)-G_1(k-1)] k^m = [G_1(n+1)(n+1)^m - G_1(1)(1)^m] - \sum_{k=1}^n G_1(k)[(k+1)^m-k^m]$$ o si lo prefiere $$G_{m+1}(n) = \left[\frac{(n+1)(n+2)}{2}(n+1)^m - 1 \right] - \sum_{k=1}^n \frac{k(k+1)}{2}[(k+1)^m-k^m].$$

Paso 2. Los dos primeros términos son los términos de frontera, como en la integración normal por partes. Como $G_m(k)$ son polinomios de grado $m+1$ y $G_1$ tiene un coeficiente principal de $1/2$ hay coeficientes $a_j$ de manera que podamos escribir

$$\sum_{k=1}^n G_1(k)[(k+1)^m-k^m] = \frac{1}{2} G_{m+1}(n) + \sum_{j=1}^m a_j G_j(n).$$

Paso 3. Sustituyendo y resolviendo para $G_{m+1}(n)$ da $$\frac{3}{2} G_{m+1}(n)= \left[\frac{(n+1)(n+2)}{2}(n+1)^m - 1\right] - \sum_{j=1}^m a_j G_j(n).$$ Tomando nota de las órdenes de $G_j$ es evidente que $G_{m+1}$ tiene orden $m+2$ .

Answer 3

Definamos

$$S_p(n) = \sum_{k=0}^n k^p$$

Desde $k^p=k\cdot k^{p-1}$ podemos escribir

$$\begin{align} S_p(n) = &1^{p-1} +\\ &2^{p-1} + 2^{p-1} +\\ &3^{p-1} + 3^{p-1} + 3^{p-1} +\\ &\vdots\\ &n^{p-1} + n^{p-1} + ... + n^{p-1} \end{align}$$

Podemos añadir esta suma columna por columna . Para $p=2$ y $p=3$ esto tiene una bonita interpretación como contar el número de cubos en pilas de objetos 3d yendo una sección transversal plana a la vez. Si hacemos esto, obtenemos

$$\begin{align} S_p(n) =& S_{p-1}(n) + \\ &(S_{p-1}(n) - 1^{p-1}) + \\ &(S_{p-1}(n) - 1^{p-1} - 2^{p-1}) +\\ &\vdots \\ &(S_{p-1}(n) - S_{p-1}(n-1))\\ =&\sum_{k=0}^{n-1}\left(S_{p-1}(n) - S_{p-1}(k)\right) \end{align}$$

Puede valer la pena detenerse aquí y utilizar esta idea de "añadir columna por columna" para derivar $S_2(n)$ de $S_1(n)$ antes de seguir leyendo.

Ahora tenemos que suponer por inducción que, para todos los $k$ menos de $p$ , $S_k(n)$ es un polinomio en $n$ de grado $k+1$ con coeficientes racionales. Por supuesto, esto es cierto para $p=1$ como puede demostrarse con el argumento de Gauss, y si has seguido mi consejo en el último párrafo sabrás que es cierto para $p=2$ también. Escribamos

$$S_p(x) = a_{p+1}x^{p+1} + a_px^p + ... a_0$$

Podemos continuar el cálculo iniciado anteriormente:

$$\begin{align} S_p(n) &= \sum_{k=0}^{n-1}(S_{p-1}(n) - S_{p-1}(k))\\ &= n S_{p-1}(n) - \sum_{k=0}^{n-1} S_{p-1}(k) \\ &= n S_{p-1}(n) - \sum_{k=0}^{n-1} \sum_{i=0}^p a_i k^i \\ &= n S_{p-1}(n) - \sum_{i=0}^{p} a_i S_i(n-1) \end{align}$$

En el último paso, hemos tomado la doble suma y hemos agrupado los términos por exponente. Puedes ver lo que estamos empezando a hacer aquí - estamos tratando de expresar $S_p(n)$ en términos de $S_k(n)$ para $k<p$ por lo que se seguirá por inducción que si todos estos últimos son polinomios en $n$ Así es $S_p(n)$ . Ahora mismo el problema es que lo que tenemos son $S_k(n-1)$ no $S_k(n)$ pero esto está bien ya que tenemos $S_k(n-1) = S_k(n) - n^k$ . Así, podemos continuar:

$$\begin{align} S_p(n)&= n S_{p-1}(n) - \sum_{i=0}^{p} a_i (S_i(n) - n^i) \\ &= n S_{p-1}(n) - \sum_{i=0}^{p} a_i S_i(n) + \sum_{i=0}^p a_i n^i \\ &= (n + 1) S_{p-1}(n) - \sum_{i=0}^{p} a_i S_i(n) \end{align}$$

Obsérvese que el lado derecho de esta ecuación contiene en realidad $S_p(n)$ Así que tenemos que "resolver para" $S_p(n)$ , obteniendo:

$$S_p(n) = (1 - a_p)^{-1}\left((n + 1) S_{p-1}(n) - \sum_{i=0}^{p-1} a_i S_i(n)\right)$$

Tenga en cuenta que esto sólo es válido si $a_p\neq -1$ por lo que tenemos que modificar nuestra hipótesis de inducción: el $S_k(n)$ no sólo son polinómicas en $n$ y de grado $k+1$ pero tienen coeficientes principales que no son iguales a $-1$ . El paso inductivo se deduce inmediatamente de nuestra última ecuación. El coeficiente principal del polinomio en $n$ que es el lado derecho es $\frac {a_p} {1 - a_p}$ y la función $\frac x {1 - x}$ envía reales positivos a reales positivos, por lo que nunca podemos obtener un coeficiente principal de $-1$ .