Demostrar que $\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}$

Question

Demostrar que $$\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}.$$

Este problema está en el capítulo sobre variables aleatorias discretas, pero no tengo ni idea de cómo hacer la sustitución.

No consigo que sea una fórmula destacada sin estropear las cosas, lo siento.

Answer 1

Coeficientes binomiales estándar

Utilizar el teorema del binomio $$ \begin{align} (1+x)^m(1+x)^n &=\sum_{k=0}^m\binom{m}{k}x^k\sum_{j=0}^n\binom{n}{j}x^j\\ &=\sum_{k=0}^m\sum_{j=0}^n\binom{m}{k}\binom{n}{j}x^{k+j}\\ &=\sum_{k=0}^m\sum_{r=k}^{k+n}\binom{m}{k}\binom{n}{r-k}x^r&&j=r-k\\ &=\sum_{r=0}^{m+n}\color{#C00000}{\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}}x^r\tag{1}\\ (1+x)^{m+n} &=\sum_{r=0}^{m+n}\color{#C00000}{\binom{m+n}{r}}x^r\tag{2} \end{align} $$ Compara los coeficientes de $x^r$ en $(1)$ y $(2)$ .

---

Coeficientes binomiales generalizados

Como menciona Michael Hardy, la fórmula es verdadera, incluso cuando $m$ y $n$ no son números enteros. Los coeficientes del binomio se pueden generalizar a cualquier número real en el argumento superior: $$ \binom{x}{k}=\frac{x(x-1)(x-2)\dots(x-k+1)}{k!}\tag{3} $$ Cuando $x$ es un número entero negativo, $(3)$ da la fórmula de los coeficientes del binomio negativo: $$ \begin{align} \binom{-n}{k} &=\frac{-n(-n-1)(-n-2)\dots(-n-k+1)}{k!}\\ &=(-1)^k\frac{(n+k-1)(n+k-2)(n+k-3)\dots n}{k!}\\ &=(-1)^k\binom{n+k-1}{k}\tag{4} \end{align} $$ El Teorema Binomial Generalizado establece que para cualquier real $m$ , $$ (1+x)^m=\sum_{k=0}^\infty\binom{m}{k}x^k\tag{5} $$ Tenga en cuenta que cuando $m$ es un número entero no negativo, $\binom{m}{k}=0$ para $k\gt m$ y así $(5)$ es un polinomio en ese caso. Utilizando $(5)$ podemos imitar la prueba para los coeficientes binomiales estándar: $$ \begin{align} (1+x)^m(1+x)^n &=\sum_{k=0}^\infty\binom{m}{k}x^k\sum_{j=0}^\infty\binom{n}{j}x^j\\ &=\sum_{k=0}^\infty\sum_{j=0}^\infty\binom{m}{k}\binom{n}{j}x^{k+j}\\ &=\sum_{k=0}^\infty\sum_{r=k}^\infty\binom{m}{k}\binom{n}{r-k}x^r&&j=r-k\\ &=\sum_{r=0}^\infty\color{#C00000}{\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}}x^r\tag{6}\\ (1+x)^{m+n} &=\sum_{r=0}^\infty\color{#C00000}{\binom{m+n}{r}}x^r\tag{7} \end{align} $$ Compara los coeficientes de $x^r$ en $(6)$ y $(7)$ .

Answer 2

Obsérvese que hemos establecido ${i \choose j} = 0$ siempre que $0 \leq j \leq i$ es falso.

\begin{align} \color{#ff0000}{\large\sum_{k = 0}^{\infty}{m \choose k}{n \choose r - k}} &= \sum_{k = 0}^{\infty}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell} \delta_{\ell, r - k} = \sum_{k = 0}^{\infty}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell} \oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\, {1 \over z^{\ell - r + k + 1}} \\[3mm]&= \oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\, {1 \over z^{1 - r}} \sum_{k = 0}^{m}{m \choose k}\left(1 \over z\right)^{k} \sum_{\ell = 0}^{n}{n \choose \ell}\left(1 \over z\right)^{\ell} \\[3mm]&= \oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\, {1 \over z^{1 - r}}\,\left(1 + {1 \over z}\right)^{m} \left(1 + {1 \over z}\right)^{n} \\[3mm]&= \oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\, {1 \over z^{m + n -r + 1}}\,\left(1 + z\right)^{m + n} = \oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\, {1 \over z^{m + n -r + 1}}\sum_{k = 0}^{r + n}{r + n \choose k}z^{k} \\[3mm]&= \sum_{k = 0}^{m + n}{m + n \choose k} \oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\, {1 \over z^{m + n - r + 1 - k}} = \sum_{k = 0}^{m + n}{m + n \choose k}\delta_{m + n - r,k} \\[3mm]&= {m + n \choose m + n - r} = \color{#ff0000}{\large{m + n \choose r}} \end{align}

Answer 3

Piensa en elegir un subconjunto de tamaño $r$ de un conjunto de tamaño $m+n$ . Simplemente puede elegirlo, y puede hacerlo en

$${m+n} \choose r$$

maneras, o puede elegir primero un subconjunto de tamaño $k$ de $m$ y luego un subconjunto de tamaño $r-k$ de $n$ . Y puedes hacer esto para $k=0,1,\ldots,r$ en

$${m \choose k }{n \choose r-k}$$

formas.

Answer 4

La identidad de Vandermonde $$ \sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r} $$ es realmente cierto incluso cuando $m$ y $n$ no son números enteros. Pero supongamos que tenemos una comisión en el Senado formada por $m$ Demócratas y $n$ Republicanos. El número de formas de elegir un subcomité de $r$ senadores es $$ \sum_{k=0}^r\Big(\text{the number of ways to choose $ k $ Democrats AND $ r-k $ Republicans}\Big). $$ Debes asociar la palabra "y" con la multiplicación.

Por lo que sé, hay que recurrir a otros métodos cuando $m$ o $n$ no es un número entero o es negativo.

PS: Cuando $m$ no es un número entero o es negativo, entonces $\dbinom m k$ se define como $$ \frac{m(m-1)(m-2)\cdots(m-k+1)}{k!}. $$ Cuando $m$ es un número entero no negativo, entonces esto es lo mismo que $\dfrac{m!}{k!(m-k)!}$ .