Prueba combinatoria de ∑i=0m2n−i(ni)(mi)=∑i=0m(n+m−im)(ni)∑i=0m2n−i(ni)(mi)=∑i=0m(n+ m−im)(ni) \sum \limits_{i = 0} ^{m} 2^{ni} {n \choose i}{m \choose i} = \sum\limits_{i=0}^m { n + m - yo \elegir m} {n \elegir i}

Tienes$n$mujeres en una habitación y$m$hombres en otro. Seleccionas un total de$m$personas de los ocupantes combinados de las dos habitaciones y enviarlos a una conferencia sobre combinatoria. Luego, elige un subconjunto de las mujeres restantes y las envía a una conferencia sobre topología, y envía a todos los demás a casa. Dejar$i$sea ​​el número de mujeres enviadas a la conferencia sobre combinatoria; entonces hay$\binom{n}i\binom{m}{m-i}2^{n-i}=\binom{n}i\binom{m}i2^{n-i}$formas de hacer la selección, por lo que el número total de posibilidades es

$$\sum_{i=0}^m\binom{n}i\binom{m}i2^{n-i}\;.$$

Alternativamente, puede seleccionar$i$mujeres para ser enviadas a casa, y luego de los ocupantes restantes de las dos habitaciones seleccionar$m$para asistir a la conferencia de combinatoria; el restante$n-i$las mujeres asistirán a la conferencia de topología. Claramente esto se puede hacer en

$$\sum_{i=0}^n\binom{n}i\binom{n+m-i}m$$

maneras. (Tenga en cuenta que$i$puede ser tanto como$n$en este enfoque, por lo que la suma debería tener$n$como límite superior.) Cada procedimiento envía$m$personas a la lección de combinatoria y un subconjunto de las mujeres restantes a la lección de topología, y cada una permite todas las asignaciones posibles de ese tipo, por lo que cuentan lo mismo.

Dejar$A,B$ser disjunto con$|A|=n$y$|B|=m$.

En el lado izquierdo, reemplace$\binom{m}{i}=\binom{m}{m-i}$.

Dejar

$$T=\left\{(C_1,C_2)\mid C_1\subseteq A\cup B, C_2\subseteq A, |C_1|=m, C_1\cap C_2=\emptyset\right\}$$

Definir$f,g:T\to \mathbb N$por:

$$\begin{align} f&:(C_1,C_2)\mapsto |C_1\cap A|\\ g&:(C_1,C_2)\mapsto |C_2| \end{align}$$

El

$$|T|=\sum_{i=0}^{\infty} \left|f^{-1}(i)\right| = \sum_{i=0}^{\infty} \left|g^{-1}(i)\right|$$

Ahora,$f^{-1}(i)$se puede contar seleccionando$i$elementos de$A$y$m-i$elementos de$B$Llegar$C_1$, y luego cualquier subconjunto de los restantes$n-i$elementos de$A$Llegar$C_2$. Entonces

$$\left|f^{-1}(i)\right| = 2^{n-i}\binom{n}{i}\binom{m}{m-i}$$

Y$g^{-1}(i)$se puede contar seleccionando$i$elementos de$A$para$C_2$, y luego cualquier$m$elementos del resto$m+n-i$elementos de$A\cup B$Llegar$C_1$. Entonces

$$\left|g^{-1}(i)\right|= \binom{n}{i}\binom{n+m-i}{m}$$

Por último, los recuentos de$f^{-1}$son cero si$i>m$y el conteo de$g^{-1}$son ero para$i>n$, apoyando mi comentario anterior de que la pregunta debe corregirse para tener$\sum_{i=0}^n$a la derecha, no$\sum_{i=0}^m$.

Permítanme observar que también hay una prueba algebraica simple. Tenga en cuenta la corrección en el límite superior de la RHS.

Supongamos que estamos tratando de demostrar que

$$\sum_{q=0}^m {m\choose q} 2^{n-q} {n\choose q} = \sum_{q=0}^n {n+m-q\choose m} {n\choose q}$$ dónde$n\ge m.$

Introducir la representación integral

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

que da para el LHS

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^n\times (1+z)^n}{z} \sum_{q=0}^m {m\choose q} \frac{1}{(2z)^{q}}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^n\times (1+z)^n}{z} \left(1+\frac{1}{2z}\right)^m \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^{n-m}\times (1+z)^n}{z^{m+1}} (1+2z)^m \; dz.$$

Para el RHS introducir la representación integral

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

que da para el RHS

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m}}{z^{m+1}}\; \sum_{q=0}^n {n\choose q} \frac{1}{(1+z)^q}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+m}}{z^{m+1}}\; \left(1+\frac{1}{1+z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m}}{z^{m+1}} (2+z)^n \; dz.$$

Ahora pon$z=2w$para obtener

$$\frac{1}{2\pi i} \int_{|w|=\epsilon/2} \frac{(1+2w)^{m}}{(2w)^{m+1}} (2+2w)^n \; 2 \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon/2} 2^{n-m} \frac{(1+2w)^{m}}{w^{m+1}} (1+w)^n \; dw.$$

Esto coincide con la integral para LHS, hecho.

Observación. No es difícil extraer coeficientes de esta integral, pero eso no es necesario porque la igualdad de las dos integrales es suficiente (también tenga en cuenta que todas las sumas involucradas son finitas).