Prueba

Question

Para $m,n\in\mathbb{N},\;n\geq m$, de probar lo siguiente:

$$ \etiqueta{i}\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+......+\binom{m}{m} = \binom{n+1}{m+1} $$ $$ \etiqueta{ii}\binom{n}{m}+2\binom{n-1}{m}+3\binom{n-2}{m}+......+(n-m+1)\binom{m}{m} = \binom{n+2}{m+2} $$

Mi Intento:

Para $(\mathrm{i})$, podemos escribir $\binom{n}{m}$ como el coeficiente de $x^m$$(1+x)^n$. Así también podemos escribir $\binom{n-1}{m}$ como el coeficiente de $x^m$ $(1+x)^{n-1}$ $\binom{n-2}{m}$ como el coeficiente de $x^m$$(1+x)^{n-2}$. Así que tenemos que encontrar el coeficiente de $x^m$ en

$$ (1+x)^n+(1+x)^{n-1}+(1+x)^{n-2}+........+(1+x)^{m} $$

Usando la fórmula para la suma de una progresión geométrica, esta suma es igual a

$$\frac{(1+x)^{n+1}-(1+x)^m}{x}$$

Así que ahora tenemos que encontrar el coeficiente de $x^m$ en

$$ \frac{(1+x)^{n+1}-(1+x)^m}{x} $$

o, equivalentemente, tenemos que encontrar el coeficiente de $x^{m+1}$ en $$ (1+x)^{n+1}-(1+x)^m = \binom{n+1}{m+1} $$

Podemos usar un método similar para solucionar $(\mathrm{ii})$. Puede que estas preguntas pueden resolverse utilizando los métodos combinatorios en su lugar?

Answer 1

Primer problema: Tenemos $n+1$ diferentes donas (etiquetados $1$$n+1$) alineados en una fila, y desea elegir a $m+1$ de ellos para el desayuno. Esto se puede hacer en $\binom{n+1}{m+1}$ maneras. Que nos permiten contar de otra manera.

Tal vez el más a la izquierda de anillos elegido es $1$. Hay $\binom{n}{m}$ formas de elegir el resto.

Tal vez el más a la izquierda de anillos elegido es $2$. Hay, a continuación, $\binom{n-1}{m}$ formas de elegir a los demás.

Y así sucesivamente.

Segundo Problema: Esta se realiza de manera similar. Esta vez vamos a elegir la $m+2$ buñuelos de $n+2$ donas, etiquetados $1$ $n+2$y se alinearon en ese orden.

Mira a la izquierda de dos donas elegido. Si el segundo es Rosquilla $2$, $\binom{n}{m}$ formas de elegir el resto.

Si el segundo elegido es el de Donut $3$, $2$ maneras de elegir la primera, y $\binom{n-1}{m}$ formas de elegir el resto, para un total de $2\binom{n-1}{2}$.

Si el segundo elegido es el de Donut $4$, $3$ maneras de elegir la primera, y $\binom{n-2}{m}$ formas de elegir el resto, para un total de $3\binom{n-2}{m}$.

Y así sucesivamente.

Answer 2

Supongamos $n \geq m$ y hay un conjunto de $S$ $n + 2$ objetos, que se denota como $o_1, o_2, \cdots, o_{n+2}$. Su tarea de la muestra $m + 2$ objetos de $S$. Deje $X_i$ denotar el número de formas de elegir los $m + 2$ objetos tales que el objeto de la segunda mínimo id es $o_i$. Fácil ver que $$ X_i = (i-1) \cdot { n + 2 - i \elegir m } $$ Así tenemos $$ \sum_{i=2}^{n+2-m} X_i = {n \elegir m} + 2\cdot{n-1 \elegir m} + \cdots + (n + 1 -m) \cdot {m \elegir m} = {n + 2 \elegir m + 2} $$

---

Similar derivación puede ser aplicado a (i) con alguna modificación menor. En lugar de enumerar el segundo identificador mínimo, debe enumerar el identificador mínimo en su lugar.

Answer 3

Tal vez un poco tarde pero aquí está mi respuesta:

Considere la posibilidad de contar el número de bits posibles cadenas de longitud $n+i$: $$ \underbrace{111...\overbrace{\textbf{1}}^{i^{\text{th}}\ 1}...111}_{m+i\ 1\text{s}}\ 000...000 $$ Así que, aquí $n$ es el número de dígitos a la derecha de la $i^\text{th}\ 1$. El número de cadenas de bits está dado simplemente por $\binom{n+i}{m+i}$ donde $m$ es el número de $1$s a la derecha de la $i^{\text{th}}\ 1$.
También podemos contar de cadenas de bits para cada posible posición de la $i^{\text{th}}\ 1$ (es decir, la posición $i$, posición $i+1$ hasta la posición $i+n-m$) y la suma de estos a dar el mismo resultado.
Cuando la $i^{\text{th}}\ 1$ está en la posición $i+r$ hay $i+r-1$ dígitos a la izquierda, incluyendo $i-1$ $1$s y $n-r$ dígitos a la derecha, incluidos los $m$ $1$s.
Así que si nos suma más de $r$:
$$\dbinom{n+i}{m+i} = \sum_{r=0}^{n-m} \dbinom{i+r-1}{i-1}\dbinom{n-r}{m} $$ Los dos ejemplos son casos especiales de esta identidad.
Si ponemos $i=1$ $i=2$ tenemos a los dos resultados que se requieren:
$$\dbinom{n+1}{m+1} = \sum_{r=0}^{n-m} \dbinom{r}{0}\dbinom{n-r}{m} = \sum_{r=0}^{n-m} \dbinom{n-r}{m} = \dbinom{n}{m} + \dbinom{n-1}{m} + ... + \dbinom{m}{m} $$ y
$$\dbinom{n+2}{m+2} = \sum_{r=0}^{n-m} \dbinom{r+1}{1}\dbinom{n-r}{m} = \sum_{r=0}^{n-m} \left(r+1\right)\dbinom{n-r}{m} = 1\dbinom{n}{m} + 2\dbinom{n-1}{m} + ... + \left(n-m+1\right)\dbinom{m}{m} $$