Construir una prueba combinatoria de una identidad Binomial

Question

Tenga en cuenta: $$\sum_{k=0}^m \binom{n+k}k = \binom{m+n+1}m.$ $

El lado izquierdo cuenta el número de subconjuntos cuyo tamaño es igual a su elemento máximo y un valor fijo. Como alternativa, podemos elegir cuántas formas hay para escoger un subconjunto de % tamaño máximo $k=m$de la máxima conjunto $m+n+1.$ sin embargo, estoy en una pérdida en cuanto a qué hacer con esta información.

Answer 1

'Subconjuntos de qué?" parece una pregunta razonable preguntar. Su interpretación es un poco confusa, el mayor conjunto considerado en el LHS es uno menor que el de la derecha, y usted no sabe el subconjunto del elemento maximal en el lado izquierdo, sólo el más grande podría ser.

Teniendo en cuenta lo que dices acerca de la RHS, vamos a $S = \{1, 2, \cdots, n-1, n, n+1, \cdots, n+m+1\}$. A continuación, el lado derecho es el número posible de tamaño $m$ subconjuntos.

Para la LHS, proceda de la siguiente manera:

• Cómo muchos de los subconjuntos no contienen $(n+m+1)$? Que $k$ ¿coincide?
• Cuántos subconjuntos contienen $(n+m+1)$, pero no $(n+m)$?
• Cuántos subconjuntos contienen $(n+m+1)$$(n+m)$, pero no $(n+m-1)$?
• ...

Revise todos los subconjuntos de caer en una de estas categorías.

Answer 2

El lado derecho es de cuántas maneras puedo coger $m$ bolas de $m+n+1$. Considere la posibilidad de la solución: Puedo elegir una bola. Si yo escojo que nos quedamos con $\binom{m+n}{m-1}$ si yo no recogerlo me voy a dejar con $\binom{m+n}{m}$.
A partir de esta relación recursiva de la siguiente manera: $$\binom{m+n+1}{m} = \binom{m+n}{m} + \binom{m+n}{m-1}$$ Ahora si puedo seguir para aplicar la misma regla para el $\binom{m+n}{m-1}$ voy a llegar a esa suma.
En una combinatoria declaración este será el número de maneras en que puedo coger $m$ bolas de $m+n+1$ es el número de maneras en que puedo coger $m$ bolas de $m+n$ dado que yo no recoger la bola 1, más el número de maneras si puedo coger $m-1$ bolas de $m+n-1$ I recoger la bola 1, pero no de la bola 2, más el número de maneras si puedo coger $m-2$ bolas de $m+n-2$ I recoger la bola 1 y 2, pero no 3,más ... hasta que llegue a recoger las m primeras bolas y yo estoy hecho.

Answer 3

Queremos saber el número de formas de suma $n$ números, $x_1, x_2, x_3 \ldots x_n \ge 0 $, que es menor que o igual a $m$. Que es:

$$ x_1 + x_2 + x_3 + \ldots + x_n \le m $$

Una manera de hacer esto es agregar una variable de holgura llama $x_{n+1}$, por lo que el $x_1 + x_2 + x_3 + \ldots + x_{n} + x_{n+1} = m $. Hay $\binom{m + n}{m}$ formas para resolver esta ecuación.

Otra manera de hacer esto es tener en cuenta todas las formas de suma estos $n$ números de a $0, 1, 2, \ldots m-1, m$, y se suman todas estas combinaciones. Hay $\displaystyle\sum_{k=0}^{m} \binom{k+n-1}{k} $ formas de hacerlo.

Su respuesta se desprende de dejar a $n \mapsto n+1$.