Demuestra que ∑k=0r(n+kk)=(n+r+1r)∑k=0r(n+kk)=(n+r+1r)\sum\limits_{k=0}^r\binom{ n+k}k=\binom{n+r+1}r usando argumentos combinatorios. [duplicar]

Estás en el camino correcto, pero tienes una discrepancia entre elegir$r$de$n+r+1$a la derecha, y eligiendo$r$de$n+r$a la izquierda, así que lo que tienes no funciona del todo. Aquí hay un enfoque que funciona y es bastante similar en espíritu a lo que ha intentado.

Dejar$A=\{0,1,\ldots,n+r\}$; claramente$|A|=n+r+1$, entonces$\binom{n+r+1}r$es el numero de$r$subconjuntos de tamaño$A$. Ahora veamos un término típico en el lado izquierdo. El término$\binom{n+k}k$es el número de maneras de elegir un$k$subconjunto de tamaño de$\{0,1,\ldots,n+k-1\}$; ¿Cómo encaja eso con la elección de un$r$subconjunto de tamaño de$A$?

Dejar$n+k$ser el miembro más grande de$A$que no elegimos para nuestro$r$-subconjunto de tamaño; entonces hemos elegido todos los$(n+r)-(n+k)=r-k$miembros de$A$que son mas grandes que$n+k$, por lo que debemos completar nuestro conjunto eligiendo$k$miembros de$A$que son más pequeños que$n+k$, es decir,$k$miembros del conjunto$\{0,1,\ldots,n+k-1\}$. En otras palabras, hay$\binom{n+k}k$maneras de elegir nuestro$r$subconjunto de tamaño de$A$de modo que$n+k$es el miembro más grande de$A$que no está en nuestro conjunto. Y ese número más grande que no está en nuestro conjunto no puede ser más grande que$n$, por lo que las opciones para ello son$n+0,\ldots,n+r$. De este modo,$\sum_{k=0}^r\binom{n+k}k$cuenta el$r$subconjuntos de tamaño$A$clasificándolos según el miembro más grande de$A$que no contienen .

---

Puede ser un poco más fácil ver lo que está pasando si haces uso de la simetría para reescribir la identidad como

$$\sum_{k=0}^r\binom{n+k}n=\binom{n+r+1}{n+1}\;.\tag{1}$$

Dejar$A$ser como arriba; el lado derecho de$(1)$es claramente el número de$(n+1)$subconjuntos de tamaño$A$. Ahora deja$S$ser un arbitrario$r$subconjunto de tamaño de$A$. El elemento más grande de$S$debe ser uno de los numeros$n,n+1,\ldots,n+r$, es decir, uno de los números$n+k$para$k=0,\ldots,r$. Y si$n+k$es el elemento más grande de$S$, hay$\binom{n+k}n$formas de elegir el$n$miembros más pequeños de$S$. Así, el lado izquierdo de$(1)$también cuenta el$(n+1)$subconjuntos de tamaño$A$, clasificándolos según sus elementos mayores.

La relación entre los dos argumentos es sencilla: los conjuntos que conté en el primer argumento son los complementos en$A$de los conjuntos que conté en el segundo argumento. Hay una biyección entre el$r$-subconjuntos de$A$y sus complementarios$(n+1)$-subconjuntos de$A$, por lo que su identidad y$(1)$esencialmente están diciendo lo mismo.

Dejar$d=n+1$. Trata de encontrar la dimensión del espacio de polinomios de grado menor o igual que$r$de dos maneras diferentes: El método A es directo y da la RHS. El método B suma los polinomios que tienen un grado exactamente igual a$k$para$0\leq k\leq r$.

Método A: Compruebe que el mapa$x^{\alpha}\mapsto \{1+\alpha_1,2+\alpha_1+\alpha_2,\dots,d+\alpha_1+\dots+\alpha_d\}$es una biyección del espacio de polinomios a los subconjuntos de cardinalidad$r$de$\{1,\dots,d+r\}$.

Método B: Para cada$k$encuentre un mapa similar (pero no del todo equivalente) para encontrar el número de polinomios que tienen exactamente el grado$k$. Pista: piensa en el polinomio de grado 6$x_1^2 x_2^3x_3$por ejemplo como$(1,1,2,2,2,3)$. Este pensamiento te da una identificación de polinomios con grado$k=6$con$6$dibujos de$d=3$bolas, con reemplazo de bolas después de cada sorteo. El truco ahora es nuevamente identificar algo como$(1,1,2,2,2,3)$con un subconjunto de$\{1,\dots,k+d=6+3\}$agregando a cada elemento de la lista ordenada para evitar repeticiones.

arreglar cualquier$r$del$n+r+1$objetos y etiquetarlos$A_1,A_2,...A_r.$Ahora,$n+r+1$puede o no contener todos o cualquier número del conjunto {$A_1,A_2,...A_r$}.

Caso 1-No contiene$A_1$

esto sucederá en$n+r\choose r$maneras como$r$las cosas deben elegirse entre las restantes$n+r$cosas.

Caso 2-No contiene$A_2$pero contiene$A_1$.

esto sucede en$n+r-1\choose r-1$maneras.

Estuche r-Contiene$A_1,A_2...A_{r-1}$pero no$A_r$.

esto sucederá en$n+r-(r-1)\choose 1$caminos =$n+1\choose 1$maneras.

Caso r+1- Contiene$A_1,A_2,A_3...A_r$

esto sucede en$n\choose 0$maneras.

Así, sumando obtenemos,

$$\binom n 0 + \binom {n+1} 1 + \binom {n+2} 2+\cdots+ \binom {n+r} r=\binom {n+r+1} r$$