Prueba de la identidad $\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}$

Question

Prueba la identidad: $$\sum_{k=0}^{\min[p,q]}{p\choose k}{q\choose k}{n+k\choose p+q}={n\choose p}{n\choose q}.$$

Answer 1

$$ \begin{align} \sum_k\binom{p}{k}\binom{q}{k}\binom{n+k}{p+q} &=\sum_{j,k}\binom{p}{k}\binom{q}{k}\binom{n}{p+q-j}\binom{k}{j}\tag{1}\\ &=\sum_{j,k}\binom{p}{k}\binom{n}{p+q-j}\binom{q}{j}\binom{q-j}{q-k}\tag{2}\\ &=\sum_{j}\binom{p+q-j}{q}\binom{n}{p+q-j}\binom{q}{j}\tag{3}\\ &=\sum_{j}\binom{n-q}{n-p-q+j}\binom{n}{q}\binom{q}{j}\tag{4}\\ &=\sum_{j}\binom{n-q}{p-j}\binom{n}{q}\binom{q}{j}\tag{5}\\ &=\binom{n}{p}\binom{n}{q}\tag{6} \end{align} $$ Explicación

$(1)$ $\displaystyle\binom{n+k}{p+q}=\sum_j\binom{n}{p+q-j}\binom{k}{j}$

$(2)$ $\displaystyle\binom{q}{k}\binom{k}{j}=\binom{q}{j}\binom{q-j}{q-k}$

$(3)$ $\displaystyle\sum_k\binom{p}{k}\binom{q-j}{q-k}=\binom{p+q-j}{q}$

$(4)$ $\displaystyle\binom{p+q-j}{q}\binom{n}{p+q-j}=\binom{n-q}{n-p-q+j}\binom{n}{q}$

$(5)$ $\displaystyle\binom{n-q}{n-p-q+j}=\binom{n-q}{p-j}$

$(6)$ $\displaystyle\sum_j\binom{n-q}{p-j}\binom{q}{j}=\binom{n}{p}$

Answer 2

Desde $$[x^i] (1-x)^{-(r+1)} =\binom{r+i}{i}=\binom{r+i}{r},\qquad (*)$$ podemos escribir $$ \binom{n}{p} \binom{n}{q} = [x^{n-p}y^{n-q}] (1-x)^{-(p+1)} (1-y)^{-(q+1)}. $$ Esto se puede reescribir como una integral compleja $$ \frac{1}{(2\pi i)^2} \int x^{p-n-1} y^{q-n-1} (1-x)^{-(p+1)} (1-y)^{-(q+1)} dx dy, $$ donde $x$ y $y$ ambos atraviesan pequeños círculos en sentido contrario a las agujas del reloj alrededor del origen. Ahora, haz la sustitución $$x = z\frac{1+w}{1+z}, \qquad y=w\frac{1+z}{1+w}.$$ Desde $$dx \wedge dy = \frac{1-zw}{(1+z)(1+w)} dz \wedge dw$$ esto cambia la integral a $$ \frac{1}{(2\pi i)^2} \int z^{p-n-1} w^{q-n-1} (1+w)^p (1+z)^q (1-zw)^{-(p+q+1)} dz\, dw.$$ En la superficie de la integración, $z$ y $w$ permanecerán ahora en pequeños anillos alrededor del origen. Permaneciendo dentro de la región donde el integrando es holomorfo, podemos deformar la superficie de integración hasta $z$ y $w$ se mueven en sentido contrario a las agujas del reloj en pequeños círculos alrededor del origen. Esto no cambia el valor de la integral, por lo que será igual a $$ [z^{n-p} w^{n-q}] (1+w)^p (1+z)^q (1-zw)^{-(p+q+1)}. $$ Utilizando (*) y el teorema del binomio, esto es igual a $$ \sum_{\ell\in{\Bbb Z}} \binom{p}{n-q-\ell} \binom{q}{n-p-\ell} \binom{p+q+\ell}{p+q}, $$ donde el coeficiente binomial $\binom{i}{j}$ se considera que desaparece si $j$ no está en $\{0,1,\dots,i\}$ . Sustituyendo $\ell:=n-p-q+k$ ahora da el resultado deseado.

Answer 3

He aquí una prueba de variables complejas ligeramente diferente.

Supongamos que queremos evaluar $$\sum_{k\ge 0} {p\choose k} {q\choose k} {n+k\choose p+q}$$

que se afirma que es $${n\choose p} {n\choose q}.$$

Utilizamos las integrales $${p\choose k} = \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{p-k+1}} \frac{1}{(1-z_1)^{k+1}} \; dz_1$$

y $${q\choose k} = \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{q-k+1}} \frac{1}{(1-z_2)^{k+1}} \; dz_2.$$

Estos dos controlan efectivamente el rango siendo su producto cero cuando $k\gt \min(p,q)$ para que podamos extender la suma hasta el infinito.

También utilizamos $${n+k\choose p+q} = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n+k} \; dw$$

Esto da como resultado para la suma $$\frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{1-z_1} \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{1+q}} \frac{1}{1-z_2} \\ \times \sum_{k\ge 0} \frac{(1+w)^k z_1^k z_2^k}{(1-z_1)^k (1-z_2)^k} \; dz_2 \; dz_1 \; dw \\ = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{1-z_1} \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{1+q}} \frac{1}{1-z_2} \\ \times \frac{1}{1-(1+w) z_1 z_2 / (1-z_1) / (1-z_2)} \; dz_2 \; dz_1 \; dw \\ = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{2\pi i}\int_{|z_2|=\epsilon} \frac{1}{z_2^{1+q}} \\ \times \frac{1}{(1-z_1)(1-z_2)-(1+w) z_1 z_2} \; dz_2 \; dz_1 \; dw.$$

El término interno aquí es $$\frac{1}{1-z_1-z_2 + z_1 z_2 - z_1 z_2 - w z_1 z_2} \\ = \frac{1}{1-z_1-z_2 - w z_1 z_2} = \frac{1}{1-z_1} \frac{1}{1-(1+wz_1) z_2 /(1-z_1)}.$$

Extraer el residuo en $z_2$ entonces da como resultado $$\frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{1}{1-z_1} \frac{(1+wz_1)^q}{(1-z_1)^q} \; dz_1 \; dw \\ = \frac{1}{2\pi i}\int_{|w|=\epsilon} \frac{1}{w^{p+q+1}} (1+w)^{n} \frac{1}{2\pi i}\int_{|z_1|=\epsilon} \frac{1}{z_1^{1+p}} \frac{(1+wz_1)^q}{(1-z_1)^{q+1}} \; dz_1 \; dw.$$

Por simetría de la suma inicial podemos suponer que $p\le q,$ obteniendo para la integral interna $$\sum_{m=0}^p {q\choose m} w^m {p+q-m\choose q}.$$

La integral exterior da ahora como resultado $$\sum_{m=0}^p {q\choose m} {p+q-m\choose q} {n\choose p+q-m}.$$

El término de la suma aquí es $$\frac{n!}{(q-m)! \times m! \times (p-m)! \times (n+m-p-q)!} \\ = {n\choose p} \frac{p! \times (n-p)!}{(q-m)! \times m! \times (p-m)! \times (n+m-p-q)!} \\ = {n\choose p} {p\choose m} {n-p\choose q-m}.$$

Por lo tanto, queda por demostrar que $$\sum_{m=0}^p {p\choose m} {n-p\choose q-m} = {n\choose q}$$

que puede hacerse de forma combinada o inspeccionando la integral $$\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{q+1}} (1+v)^{n-p} \sum_{m=0}^p {p\choose m} v^m \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{q+1}} (1+v)^{n-p} (1+v)^p \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{1}{v^{q+1}} (1+v)^{n} \; dv = {n\choose q}.$$