¿Cómo probar ${n+2 \choose 3}=1\cdot n + 2 \cdot (n - 1) + \ldots + n \cdot 1$?

Question

Vi este problema como un ejercicio en Identidades Combinatorias :-

Probar que $${n+2 \choose 3}=1\cdot n + 2 \cdot (n - 1) + \ldots + n \cdot 1\,.$$

Después de darle algo de tiempo a esto, creo que es bastante similar a la identidad :-

${n \choose k} = {n - 1 \choose k - 1} + {n - 1 \choose k}$

Pero no sé cómo demostrar esto algebraicamente, ¿alguien me puede ayudar con esto?

(Nótese que aún no estoy seguro de si podemos usar esa identidad o no, también puedo suponer que podemos usar la Identidad de Vandermonde aquí).

Answer 1

Sugiero probarlo combinatoriamente. $\binom{n+2}3$ es el número de subconjuntos de $3$ elementos del conjunto $[n+2]=\{1,2,\ldots,n+2\}$. Podemos clasificar esos conjuntos por sus elementos del medio: sea $\mathscr{A}_k$ la familia de todos los subconjuntos de $3$ elementos de $[n+2]$ de la forma $\{j,k,\ell\}$, donde $j; claramente

$$\binom{n+2}3=\sum_k|\mathscr{A}_k|\;.$$

Ahora prueba que $|\mathscr{A}_k|=(k-1)(n+2-k)$ y determina el rango de valores posibles de $k$ para completar la prueba.

Answer 2

Ambos son iguales al número de formas de seleccionar tres números de $1, \ldots, n+2$ : el primero por definición, el segundo eligiendo el número del medio, digamos $i+1$, y luego eligiendo uno de los $i$ disponibles "a la izquierda" para que sea el menor, y uno de los $(n+2)-(i+1)=n+1-i$ disponibles "a la derecha" para que sea el mayor.

Answer 3

Estoy seguro de que esta identidad ha sido demostrada aquí. No puedo encontrarla. Tenga en cuenta que $$\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{s}=\binom{m+1}{r+s+1}\tag{*}$$ para todos los enteros $m,r,s$ con $0\leq r,s\leq m$. Una prueba combinatoria es contar el número de $(r+s+1)$-subconjuntos de $\{0,1,2,\ldots,m\}$. Claramente, hay $\displaystyle\binom{m+1}{r+s+1}$ tales subconjuntos.

Para $k=0,1,2,\ldots,m$, hay precisamente $\displaystyle\binom{k}{r}\,\binom{m-k}{s}$ subconjuntos de tamaño $r+s+1$ tal que $k$ es el elemento $(r+1)$-ésimo más pequeño de estos conjuntos. Esto demuestra (*). Ahora, el problema del OP es cuando $m:=n+1$, $r:=1$ y $s:=1$.

Una prueba algebraica de (*) se puede ver considerando $$f(x):=\sum_{k=r}^\infty\,\binom{k}{r}x^{k-r}(1+x)^{m-k}=(1+x)^{m-r}\,\sum_{k=r}^\infty\,\binom{k}{r}\,\left(\frac{x}{1+x}\right)^{k-r}\,.$$ Así, $$\begin{align}f(x)&=(1+x)^{m-r}\,\sum_{k=0}^\infty\,\binom{k+r}{r}\,\left(\frac{x}{1+x}\right)^k \\&=(1+x)^{m-r}\,\left(1-\frac{x}{1+x}\right)^{-r-1}=(1+x)^{m+1}\,.\end{align}$$ Para cada entero $t\geq 0$, sea $[x^t]\,g(x)$ el coeficiente de $x^t$ en un polinomio $g(x)$. Entonces, $$\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{m-k-s}=[x^{m-r-s}]\,f(x)=[x^{m-r-s}]\,(1+x)^{m+1}\,.$$ Por lo tanto, $$\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{s}=\sum_{k=0}^m\,\binom{k}{r}\,\binom{m-k}{m-k-s}=\binom{m+1}{m-r-s}=\binom{m+1}{r+s+1}\,.$$

Editar. Encontré una prueba combinatoria de (*) en este viejo enlace. También se dan pruebas analíticas de (*) aquí. Las pruebas algebraicas de (*) se pueden encontrar aquí.

Answer 4

$$\sum_{k=1}^n k(n+1-k)=(n+1)\sum_{k=1}^nk-\sum_{k=1}^nk^2$$ Ahora aplicamos las identidades $$\sum_{k=1}^nk=\frac12n(n+1)\qquad\sum_{k=1}^nk^2=\frac16n(n+1)(2n+1)$$ y simplificamos el resultado.

Answer 5

Estamos tratando de demostrar que $$1\!\cdot\!n \, + \, 2\!\cdot\!(n - 1)\, + \, \ldots \, + \, n\!\cdot\!1\ = {n+2 \choose 3}$$ Peter Foreman escribió el lado izquierdo como $$\sum_{k=1}^n k(n-k+1)$$ Otra forma de escribir el lado izquierdo es $$\sum_{j=1}^n\sum_{k=1}^j k$$ El lado izquierdo suele aparecer como una sumatoria anidada dentro de otra sumatoria. Por ejemplo, en el primer día de Navidad recibes 1 regalo; en el segundo día, recibes $1+2$ regalos; en el tercer día, $1+2+3$ regalos; .... $$\sum_{j=1}^{12} \sum_{k=1}^j k = \binom{12+2}{3} = 364$$

La Identidad del Palo de Hockey se suele presentar como $$\sum_{i=r}^{m} \binom{i}{r} = \binom{m+1}{r+1}$$ Pero he encontrado útil esta versión equivalente porque la sumatoria comienza en $k=1$ y va hasta $n = m - r +1$: $$\sum_{k=1}^{n} \binom{k+r-1}{r} = \binom{n+r}{r+1}$$ Para $r=1$ $$\sum_{k=1}^{n} \binom{k}{1} = \binom{n+1}{2}$$ Para $r=2$ $$\sum_{j=1}^{n} \binom{j+1}{2} = \binom{n+2}{3}$$ Entonces, $$\begin{align*} 1\!\cdot\!n \, + \, 2\!\cdot\!(n - 1)\, + \, \ldots \, + \, n\!\cdot\!1 = \sum_{j=1}^n\sum_{k=1}^j k\ &= \sum_{j=1}^n\sum_{k=1}^j \binom{k}{1}\\ &= \sum_{j=1}^n \binom{j+1}{2}\\ &= \binom{n+2}{3} \end{align*}$$ Esto responde a la pregunta, pero el patrón continúa.

Para $r=3$ $$\sum_{i=1}^{n} \binom{i+2}{3} = \binom{n+3}{4}$$ así que $$\sum_{i=1}^{n}\sum_{j=1}^i\sum_{k=1}^j k\ = \binom{n+3}{4}$$