Encontrar un argumento combinatorio de un interesante identidad: $\sum_k \binom nk \binom{m+k}n = \sum_i \binom ni \binom mi 2^i$

Question

Considere la siguiente identidad

$${{n}\choose{0} }{m\choose n} + {n\choose 1}{{m+1} \choose n}+ \cdots +{n\choose n}{{m+n} \choose n} =\sum_{i=0}^{\min (m ,n)} {n\choose i}{m\choose i}2^i$$

El lado derecho se ve realmente bueno para mí pero no puedo encontrar cualquier combinatoria argumento para esto.Estoy totalmente atascado en la forma de enfoque. Me gustaría sugerencias y no de soluciones completas.

EDITAR supongo que pidiendo una pista estaba un poco demasiado para esta pregunta. Disculpas.

Answer 1

Ha $n$ de las mujeres en la Habitación de Un y $m$ hombres, en la Sala B. Para algunos $k\in\{0,\ldots,n\}$ que usted escoja $k$ de las mujeres y el movimiento en la Sala B; esto se puede hacer en $\binom{n}k$ maneras. A continuación, elige $n$ de las personas en la Sala B y moverlos a la Sala C; esto se puede hacer en $\binom{m+k}n$ maneras, por lo que hay un total de

$$\sum_k\binom{n}k\binom{m+k}n$$

maneras de llevar a cabo este proceso. El resultado del proceso es $n$ de personas en la Sala C, $n-k$ a las mujeres en Una Habitación para algunos $k$, e $m+k-n$ de personas en la Sala B. Si hay $\ell$ de los hombres en la Sala C, entonces hay $m-\ell$ hombres, en la Sala B.

Podríamos comenzar por simplemente recoger $\ell$ a los hombres de la Sala B y $n-\ell$ de las mujeres desde la Habitación de Un y que se muevan a la Sala de C; esto deja a $\ell$ a las mujeres en Una Habitación, y llegamos a la conclusión moviendo cualquier subconjunto de ellos en el Salón B$. Este proceso puede llevarse a cabo en

$$\sum_\ell\binom{n}{n-\ell}\binom{m}\ell2^\ell=\sum_\ell\binom{n}\ell\binom{m}\ell2^\ell$$

maneras.

Claramente los dos procedimientos tienen el mismo conjunto de resultados posibles: $n$ de las personas en la Sala C, todos los otros hombres en la Sala B, y, posiblemente, algunas de las otras mujeres en la Sala B en lugar de la Sala de A. por Lo tanto,

$$\sum_k\binom{n}k\binom{m+k}n=\sum_k\binom{n}k\binom{m}k2^k\;.$$

Answer 2

Me permito aportar una prueba de variables complejas, por la variedad de sake, que es un instructivo de ejercicio.

Supongamos que buscamos para comprobar que $$\sum_{q=0}^n {n\elegir q} {m+q\elegir n} = \sum_{q=0}^{\min(m,n)} {n\elegir q}{m\elegir q}2^q.$$ con $n,m$ una enteros positivos.

Para el LHS introducir la representación integral $${m+q\elegir n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+p}}{z^{n+1}} \; dz$$

que se da por la suma $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} \sum_{q=0}^n {n\elegir q} (1+z)^q\; dz$$

o, alternativamente, $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} (2+z)^n \; dz.$$

Para la RHS comenzar por la observación de que es simétrica en $m$ $n$ así que podemos suponer que la $m\ge n.$ Ahora introducir la integral representación

$${m\elegir q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{q+1}} \; dz$$

que se da por la suma $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \sum_{q=0}^n {n\elegir q} 2^q \frac{1}{z^p} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \left(1+\frac{2}{z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z} \frac{(z+2)^n}{z^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{n+1}} (2+z)^n \; dz.$$

Tenemos igualdad de la LHS y RHS que iba a ser mostrado.

Adenda. Si no habíamos observado la simetría aquí nos gustaría conseguir para $n\ge m$ integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{m+1}} (2+z)^m \; dz.$$

Poner $z=2/w$ en esta integral para obtener $$-\frac{1}{2\pi i} \int_{|w|=R} \frac{(1+2/w)^{n}}{(2/w)^{m+1}} (2+2/w)^m \times\left(-\frac{2}{w^2}\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(w+2)^n}{w^n} \frac{w^{m+1}}{2^{m+1}} \frac{(2w+2)^m}{w^m} \times\left(\frac{2}{w^2}\right) \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(w+2)^n}{w^{n+1}} (w+1)^m \; dw $$

que es la forma que hemos tratado.