Probar esta suma infinita de un producto de tres binomios: $\sum\limits_{s}\binom{n+s}{k+l}\binom ks\binom ls=\binom nk\binom nl$

Question

Pregunta: ¿Cómo se demuestra $$\sum\limits_{s}\binom{n+s}{k+l}\binom ks\binom ls=\binom nk\binom nl$$

No sé por dónde empezar. He intentado escribir ambos lados como el coeficiente de $x^n$ de la expansión de un binomio. Pero obviamente, eso no encaja en el lado derecho porque es el producto de dos binomios.

Supongo que necesitaremos el teorema del multinomio. ¿Es eso correcto? ¿Tienes alguna otra idea?

Answer 1

$$ \eqalign{ & \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\left( \matrix{ n + s \cr k + l \cr} \right)\left( \matrix{ k \cr s \cr} \right)\left( \matrix{ l \cr s \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{ n \cr k + l - j \cr} \right)\left( \matrix{ s \cr j \cr} \right)} \left( \matrix{ k \cr s \cr} \right)\left( \matrix{ l \cr s \cr} \right)} = \;(1) \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{ n \cr k + l - j \cr} \right)} \left( \matrix{ k \cr j \cr} \right)\left( \matrix{ k - j \cr s - j \cr} \right)\left( \matrix{ l \cr s \cr} \right)} = \; (2) \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,s\,\left( { \le \,k} \right)} {\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{ n \cr k + l - j \cr} \right)} \left( \matrix{ k \cr j \cr} \right)\left( \matrix{ k - j \cr k - s \cr} \right)\left( \matrix{ l \cr s \cr} \right)} = \; (3) \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{ n \cr k + l - j \cr} \right)\left( \matrix{ k \cr j \cr} \right)\left( \matrix{ k + l - j \cr k \cr} \right)} = \; (4)\cr & = \left( \matrix{ n \cr k \cr} \right)\sum\limits_{\left( {0\, \le } \right)\,\,j\,\left( { \le \,k + l} \right)} {\left( \matrix{ n - k \cr l - j \cr} \right)\left( \matrix{ k \cr j \cr} \right)} = \;(5) \cr & = \left( \matrix{ n \cr k \cr} \right)\left( \matrix{ n \cr l \cr} \right) \; (6) \quad \left| \matrix{ \;l,k \in \mathbb{N_0} \hfill \cr \;n \in \mathbb{C} \hfill \cr} \right. \cr} $$

donde:
- (1) convolución inversa
- (2) Revisión del trinomio en el 2º y 3º binomio
- (3) Simetría el día 3 ( $k-j$ es no negativo debido a la 2ª)
- (4) la convolución en $s$
- (5) Revisión del trinomio en el 1er y 3er binomio
- (6) convolución en $j$

Answer 2

Buscamos simplificar

$$\sum_s {n+s\choose k+l} {k\choose s} {l\choose s}.$$

La sustitución $s = t + k+l-n$ produce

$$\sum_t {t+k+l\choose k+l} {k\choose t + k+l-n} {l\choose t+k+l-n}.$$

Trabajando con la suposición de que los parámetros son enteros positivos encontramos que a partir del primer coeficiente binomial obtenemos que para que sea sea distinto de cero debemos tener $t\ge 0$ o $t\lt -(k+l).$ Sin embargo, hay que tener en cuenta que en este último caso los dos coeficientes restantes desaparecen, lo que deja $t\ge 0.$ Reescribiendo encontramos

$$\sum_{t\ge 0} {t+k+l\choose k+l} {k\choose n-l-t} {l\choose n-k-t}.$$

Introducimos representaciones integrales para los dos coeficientes de la derecha que también hacen cumplir el hecho de que $t\le n-l$ y $t\le n-k$ para que podamos podemos entonces dejar que $t$ hasta el infinito. Utilizamos

$${k\choose n-l-t} = \frac{1}{2\pi i} \int_{|z|=\epsilon_1} \frac{1}{z^{n-l-t+1}} (1+z)^k \; dz$$

así como

$${l\choose n-k-t} = \frac{1}{2\pi i} \int_{|v|=\epsilon_2} \frac{1}{v^{n-k-t+1}} (1+v)^l \; dv.$$

Entonces obtenemos para la suma (no hay problemas de convergencia aquí)

$$\frac{1}{2\pi i} \int_{|z|=\epsilon_1} \frac{1}{z^{n-l+1}} (1+z)^k \frac{1}{2\pi i} \int_{|v|=\epsilon_2} \frac{1}{v^{n-k+1}} (1+v)^l \sum_{t\ge 0} {k+l+t\choose k+l} v^t z^t \; dv\; dz. \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon_1} \frac{1}{z^{n-l+1}} (1+z)^k \frac{1}{2\pi i} \int_{|v|=\epsilon_2} \frac{1}{v^{n-k+1}} (1+v)^l \frac{1}{(1-vz)^{k+l+1}} \; dv\; dz.$$

Vemos que esto desaparece cuando $n\lt k$ o $n\lt l$ , que etiquetamos como caso A. El caso B es que $n\ge k,l.$ Evaluamos la integral interna utilizando el hecho de que los residuos suman cero. Teniendo esto en cuenta, escribimos

$$\frac{(-1)^{k+l+1}}{2\pi i} \int_{|z|=\epsilon_1} \frac{1}{z^{n+k+2}} (1+z)^k \frac{1}{2\pi i} \int_{|v|=\epsilon_2} \frac{1}{v^{n-k+1}} (1+v)^l \frac{1}{(v-1/z)^{k+l+1}} \; dv\; dz.$$

Por lo tanto, requerimos para el polo en $v=1/z$

$$\frac{1}{(k+l)!} \left(\frac{1}{v^{n-k+1}} (1+v)^l\right)^{(k+l)}$$

que es (aplica Leibniz)

$$\frac{1}{(k+l)!} \sum_{q=0}^{k+l} {k+l\choose q} (-1)^q {n-k+q\choose q} \frac{q!}{v^{n-k+1+q}} \\ \times {l\choose k+l-q} (k+l-q)! (1+v)^{l-(k+l-q)} \\ = \sum_{q=0}^{k+l} (-1)^q {n-k+q\choose q} \frac{1}{v^{n-k+1+q}} {l\choose k+l-q} (1+v)^{q-k}.$$

Evaluar en $v=1/z$ para conseguir

$$\sum_{q=0}^{k+l} (-1)^q {n-k+q\choose q} z^{n-k+1+q} {l\choose k+l-q} \frac{(1+z)^{q-k}}{z^{q-k}}.$$

Sustituyendo esto en la integral de $z$ y al voltear el signo se obtiene

$$(-1)^{k+l} \sum_{q=0}^{k+l} (-1)^q {n-k+q\choose q} {l\choose k+l-q} {q\choose k}.$$

Ahora tenemos

$${q\choose k} {n-k+q\choose q} = \frac{(n-k+q)!}{k! \times (q-k)! \times (n-k)!} = {n\choose k} {n-k+q\choose n}$$

y obtenemos

$$(-1)^{k+l} {n\choose k} \sum_{q=0}^{k+l} (-1)^q {l\choose k+l-q} {n-k+q\choose n} \\ = {n\choose k} \sum_{q=0}^{k+l} (-1)^q {l\choose q} {n+l-q\choose n} \\ = {n\choose k} [w^n] \sum_{q=0}^{k+l} (-1)^q {l\choose q} (1+w)^{n+l-q} \\ = {n\choose k} [w^n] (1+w)^{n+l} \sum_{q=0}^{k+l} (-1)^q {l\choose q} \frac{1}{(1+w)^q} \\ = {n\choose k} [w^n] (1+w)^{n+l} \left(1-\frac{1}{1+w}\right)^l \\ = {n\choose k} [w^n] w^l (1+w)^{n} = {n\choose k} {n\choose n-l} = {n\choose k} {n\choose l}.$$

Esta es la afirmación que hemos demostrado para el caso B.

Observación. Para ser perfectamente rigurosos también tenemos que demostrar que la contribución del residuo en el infinito es cero. Encontramos

$$\mathrm{Res}_{v=\infty} \frac{1}{v^{n-k+1}} (1+v)^l \frac{1}{(1-vz)^{k+l+1}} \\ = - \mathrm{Res}_{v=0} \frac{1}{v^2} v^{n-k+1} \frac{(1+v)^l}{v^l} \frac{1}{(1-z/v)^{k+l+1}} \\ = - \mathrm{Res}_{v=0} \frac{1}{v^2} v^{n-k-l+1} (1+v)^l \frac{v^{k+l+1}}{(v-z)^{k+l+1}} \\ = - \mathrm{Res}_{v=0} v^{n} (1+v)^l \frac{1}{(v-z)^{k+l+1}} = 0$$

y el cheque pasa.

Answer 3

$$\begin{align} \sum_s \color{blue}{\binom {n+s}{k+l}}\binom ks\binom ls &=\sum_s\color{blue}{\sum_j\binom n{k+j}} \color{green}{\binom ks} \underbrace{\binom ls\color{blue}{\binom s{l-j}}} _{=\color{orange}{\binom l{l-j}\binom{j}{s-l+j}}} \\ &=\sum_j\binom n{k+j}\color{orange}{\binom l{l-j}} \underbrace{\sum_s \color{green}{\binom k{k-s}}\color{orange}{\binom j{s-l+j}}}_{*=\binom{k+j}{k-l+j}=\color{pink}{\binom{k+j}{l}}}\\ &=\sum_j \binom l{l-j} \underbrace{\binom n{k+j} \qquad \color{pink}{\binom {k+j}l}} _{=\color{magenta}{\binom nl\binom {n-l}{k+j-l}}}\\ &=\color{magenta}{\binom nl} \underbrace{\sum_j \binom l{l-j} \color{magenta}{\binom{n-l}{k+j-l}}}_{*=\color{red}{\binom nk}}\\ &=\color{red}{\binom nk \binom nl} \end{align}$$ * utilizando el Identidad Vandermonde .