Evaluar $\sum\limits_{k=1}^n k^2$ y $\sum\limits_{k=1}^n k(k+1)$ combinatorially

Question

$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$

Para la primera, yo era capaz de expresar $k^2$ en términos de los coeficientes binomiales mediante la consideración de un conjunto de $X$ de cardinalidad $2k$ y particionado en dos subconjuntos $A$$B$, cada una con cardinalidad $k$. Entonces, el número de maneras de elegir de 2 elementos de los subconjuntos de a $X$ es $$\binom{2k}{2} = 2\binom{k}{2}+k^2$$ So sum $$\sum_{k=1}^n k^2 =\sum_{k=1}^n \binom{2k}{2} -2\sum_{k=2}^n \binom{k}{2} $$ $$ \qquad\qquad = \color{red}{\sum_{k=1}^n \binom{2k}{2}} - 2 \binom{n+1}{3} $$ estoy atascado en este punto a evaluar la primera de las sumas. ¿Cómo evaluar?

Necesito encontrar una expresión similar para $k(k+1)$ para la segunda suma anteriormente señalados. He tenido éxito en este momento. (Si el anterior problema se hace a continuación, así es esto, pero sería bueno saber si hay mejores enfoques o identidades que se pueden utilizar.)

Actualización: tengo el segundo. Considere la posibilidad de $$\displaystyle \binom{n+1}{r+1} = \binom{n}{r}+\binom{n-1}{r}+\cdots + \binom{r}{r}$$ Can be shown using recursive definition. Now multiply by $r!$ and set $r=2$

Answer 1

Para $$\sum_{k=1}^n (k+1)(k),$$ permítame contarle una historia.

Hay $n+2$ sillas en fila, y tres personas, Zurdo, Alice y Bob.

Ellos quieren sentarse. El zurdo no le gusta tener a nadie a su izquierda. De cuántas maneras pueden sentarse?

El zurdo podría ser en el tercer asiento de la derecha, dejando $2$ opciones de Alicia y, a continuación, $1$ para Bob. O de lo contrario el Zurdo podría estar en el cuarto puesto de la derecha, dejando $3$ opciones de Alicia y, a continuación, $2$ para Bob. Y así sucesivamente. Finalmente, el Zurdo podría estar en el extremo izquierdo del asiento, dando Alice $n+1$ opciones y Bob $n$. Por lo que el número total de asientos es nuestra suma.

O bien elija $3$ escaños $n+2$, la reserva de la izquierda para el Zurdo. Para cada opción de $3$ asientos hay, a continuación, $2$ lugares para Alice para sentarse, para un total de $$2\binom{n+2}{3}.$$

Answer 2

Mostramos bijectively que

$$2^2+4^2+6^2+\cdots +(2n)^2=\binom{2n+2}{3}.$$

Que no acaba de dar una puramente combinatoria expresión para $1^2+2^2+ \cdots +n^2$, ya que todavía tenemos que dividir por $4$, que es "álgebra". Pero el pecado de multiplicar o dividir por una constante que parece ser una pequeña en este juego. Y el resultado es muy interesante.

Imaginar la elección de $3$ números de los números de $1, 2, \dots, 2n+2$. Esto se puede hacer en $\binom{2n+2}{3}$ maneras.
Vamos a mostrar que el número de opciones es también $$2^2+4^2+6^2+\cdots +(2n)^2.$$

Tal vez el mayor número elegido es $2k+1$ o $2k+2$. Si es $2k+1$, los otros dos pueden ser elegidos en $\binom{2k}{2}$ formas, y si es $2k+2$, luego los otros dos pueden ser elegidos en $\binom{2k+1}{2}$ maneras. El uso de "álgebra", nos encontramos con que

$$\binom{2k}{2}+\binom{2k+1}{2}= (2k)^2.$$

Tome $k=1, 2, 3, \dots, n$. Llegamos a la conclusión de que el número de maneras de elegir a $3$ números de $1, 2, \dots, 2n+2$ es

$$2^2+4^2+6^2+\cdots +(2n)^2.$$

Dado que el número de opciones es claramente $\binom{2n+1}{3}$, esto casi termina el argumento. (En una nota al final de este post, nos ocupamos de la menor tarea de eliminar el uso del álgebra.)

Comentario: Si permitimos que la división por $4$, podemos concluir que $$1^2+2^2+\cdots +n^2=\frac{1}{4}\binom{2n+2}{3}.$$

Yo solía pensar que en la expresión usual $\frac{(n)(n+1)(2n+1)}{6}$ para la suma de los primeros a $n$ plazas, el $2n+1$ de alguna manera es el extraño término, que no encaja en. Pero lo hace! En realidad, es $n$ $n+1$ que son extraños. Podemos pensar de $(n)(n+1)(2n+1)$ `realmente" ser $(1/4)[(2n)(2n+1)(2n+2)]$.

Limpieza: Hay una forma estándar para evitar el `cálculo" $$\binom{2k}{2}+\binom{2k+1}{2}= (2k)^2.$$

La integridad nos muestran bijectively que para cualquier $m$, en particular,$m=2k$, tenemos
$$\binom{m}{2} +\binom{m+1}{2}=m^2.$$

Para dejar $M$ ser la colección de $\left\{1,2,3,\dots,m\right\}$. A continuación, el número de pares ordenados $(a,b)$$a$$b$$M$$m^2$. Estos pares ordenados son de dos tipos: (i) los con $a<b$ y (ii) los con $a \ge b$. El número de pares ordenados $(a,b)$ $a<b$ es sólo $\binom{m}{2}$. Los pares ordenados $(a,b)$ $a \ge b$ están en un entorno natural bijection con los pares ordenados $(b,a+1)$$b<a+1$, y $\binom{m+1}{2}$ de estos.

Answer 3

La historia de André se puede continuar: Bob estaba feliz de que él siempre tuvo menos sillas para elegir. Así que Alice y Bob decidió elegir a su presidente en el mismo tiempo. Si ambos eligen la misma silla que compartió el presidente. Así que si el Zurdo eligió el segundo asiento de la derecha Alice y Bob tuvo que seleccionar en el primer asiento. El zurdo podría seleccionar el tercer asiento dejando $2$ posibilidades a Alice y $2$ posibilidades a Bob. El zurdo podría seleccionar a la izquierda de la silla (silla con número $n+1$) lo que les otorga $n$ posibilidades para elegir. Por lo que el número total de arreglos ahora $$\sum_{k=1}^n k^2$$ De nuevo podemos calcular las posibilidades de otro modo: Seleccione 3 sillas de $n+1$ sillas, el de la izquierda es para el Zurdo de las dos restantes pueden ser asignados a Alice y Bob. Este es el caso cuando Alice y Bob elegir asientos diferentes y el número de $$2\binom{n+1}{3}$$ Cuando seleccionamos sólo 2 de las $n+1$ sillas, el de la izquierda es para el Zurdo y el segundo debe ser compartida por Alice y Bob. Esto le da $$\binom{n+1}{2}$$ posibilidades. El número de todas las posibles selecciones es la suma de los dos números que se $$2\binom{n+1}{3}+\binom{n+1}{2} = n(n+1)(2n+1)/6$$

Answer 4

Respecto de la primera, también existe la elegante fórmula (que he encontrado gracias a OEIS) $$ \sum\limits_{k = 1}^n {k^2 } = {n+2 \elegir 3} + {n+1 \elegir 3}. $$ Para una prueba, la primera nota que tiene para $n=1,2$. Ahora, indican que la expresión en el lado derecho por $a_n$. A continuación, $$ a_n - a_{n-1} = {n+2 \elegir 3} - {n \elegir 3} = \frac{{n(n + 1)(n + 2)}}{6} - \frac{{n(n - 1)(n - 2)}}{6} = \frac{{n(6n)}}{6} = n^2 . $$ Así hemos terminado, ya que también $$ \sum\limits_{k = 1}^n {k^2 } - \sum\limits_{k = 1}^{n - 1} {k^2 } = n^2 . $$