Prueba $1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3}$

Question

Pruébalo:

$$ 1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3} $$

Ahora, si simplifico la expresión combinatoria de la derecha, se reduce a $\frac{n(n+1)(2n+1)}{6}$ que es bien conocido y se puede derivar por el método de las diferencias comunes.

Sin embargo, esto es en la hoja de ejercicios relacionados con la combinatoria y específicamente el método de prueba por doble conteo. No consigo averiguar cómo se hace eso. Concretamente esto parece "elige 2 objetos de n+1 y luego elige 3 objetos de n+1 dos veces". Pero eso es todo, no encuentro relación entre eso y la suma de cuadrados. ¿Alguna ayuda?

Answer 1

La identidad es una aplicación de La identidad de Worpitzky con Números eulerianos . El teorema de Worpitzky dice: $$x^n=\sum_{k=0}^{n}A(n,k) \binom{x+k}{n}$$ donde el número euleriano $A(n, k)$ se define como el número de permutaciones de los números del 1 al n en las que exactamente k elementos son mayores que el elemento anterior (permutaciones con k "ascensos"). (La identidad de Worpitzky no es difícil de demostrar utilizando la inducción, por cierto)

Por la identidad de Worpitzky, para el entero $k\geq 1, k^2=\sum_{i=0}^{2} A(2,i) \binom{n+i}{2} = A(2,0)\binom{k}{2} +A(2,1)\binom{k+1}{2}=\binom{k}{2}+\binom{k+1}{2}$ .

Así que la suma de los cuadrados de la primera $n$ enteros positivos es \begin {Ecuación} \begin {alineado} \sum_ {i=1}^{n} k^2 &= \sum_ {i=1}^{n} \binom {k}{2} + \sum_ {i=1}^{n} \binom {k+1}{2} \\ &= \binom {n+1}{3}+ \binom {n+2}{3} \\ &= \frac {1}{6}n(n+1)(2n+1) \end {alineado} \end {Ecuación} Esta igualdad se desprende de la siguiente identidad para la suma creciente de los coeficientes del binomio: $$\sum_{j=0}^{n} \binom{j}{m} = \binom{n+1}{m+1}$$

Del mismo modo, podemos encontrar la suma de los primeros n números cúbicos. Para los números enteros $k\geq 1$ La identidad de Worpitzky dice que $k^3=A(3,0)\binom{k}{3}+A(3,1)\binom{k+1}{3}+A(3,2)\binom{k+2}{3}=\binom{k}{3}+4\binom{k+1}{3}+\binom{k+2}{3}$

Igual que acabamos de hacer en el último caso, la suma de los cubos del primer $n$ enteros positivos es \begin {Ecuación} \begin {alineado} \sum_ {i=1}^{n} k^3 &= \sum_ {i=1}^{n} \binom {k}{3} + 4 \sum_ {i=1}^{n} \binom {k+1}{3}+ \sum_ {i=1}^{n} \binom {k+2}{3} \\ &= \binom {n+1}{4}+4 \binom {n+2}{4}+ \binom {n+3}{4} \\ &= \frac {1}{4}(n^4+2n^3+n^2) \end {alineado} \end {Ecuación}

Answer 2

(Ejercicio 1.42 en Balakrishnan, Combinatorics, Schaum's Outline of Combinatorics) . Desde

$$\binom{k}{1}+2\binom{k}{2}=k+2\frac{k\left( k-1\right) }{2}=k^{2},$$

obtenemos

$$\begin{eqnarray*} S &:&=\sum_{k=1}^{n}k^{2}=\sum_{k=0}^{n}\binom{k}{1}+2\binom{k}{2} =\sum_{i=1}^{n}\binom{k}{1}+2\sum_{k=1}^{n}\binom{k}{2} \\ &=&\binom{n+1}{2}+2\binom{n+1}{3} \\ &=&\frac{n\left( n+1\right) \left( 2n+1\right) }{6}. \end{eqnarray*}$$

Answer 3

Puedes reducir esta suma a algo más manejable $$ \sum_{k=1}^Nk^2-\sum_{k=1}^Nk=\sum_{k=1}^Nk(k-1)=2\sum_{k=1}^N\binom{k}{2} $$ Ahora usa la identidad del triángulo de Pascal $\binom{n}{m}+\binom{n}{m+1}=\binom{n+1}{m+1}$ para encontrar $\binom{k}{2}=\binom{k+1}3-\binom{k}3$ para expresar esto como una suma telescópica.

Interpretación de $\sum_{k=1}^N\tbinom{k}{2}$ : Elige cualquier número entero $k$ de $1$ a $N+1$ y luego elegir dos números por debajo de $k$ . Esto es lo mismo que elegir tres enteros entre $1$ y $N+1$ .