Prueba combinatoria de una identidad binomial: $\sum_k \binom {2r} {2k-1}\binom{k-1}{s-1} = 2^{2r-2s+1}\binom{2r-s}{s-1}$

Question

Debo encontrar un argumento combinatorio para la siguiente identidad:

$$\sum_k \binom {2r} {2k-1}\binom{k-1}{s-1} = 2^{2r-2s+1}\binom{2r-s}{s-1}$$

Para el lado derecho, yo estaba pensando que sólo sería el número de formas de elegir al menos $s-1$ elementos de un $[2r-s]$ conjunto. Sin embargo, para el lado izquierdo, no sé realmente lo que está representando.

Cualquier ayuda será muy apreciada.

Answer 1

PISTA: Tenemos $2r-s$ bolas blancas numeradas $1$ a través de $2r-s$ . Elegimos $s-1$ de ellas y pintamos esas bolas de rojo, y pegamos estrellas doradas en cualquier subconjunto de las bolas blancas restantes; como hay $2r-s-(s-1)=2r-2s+1$ bolas blancas restantes, hay $$\binom{2r-s}{s-1}2^{2r-2s+1}$$ posibles resultados de esta secuencia de operaciones.

Como alternativa, podemos empezar con $2r$ bolas blancas numeradas $1$ a través de $2r$ . Elegimos un número impar de estas bolas, $2k-1$ para algunos $k\in[r]$ y alinearlos en orden numérico. El $k$ -la bola en línea es la que está en el centro; llámala $B$ . Elegimos $s-1$ de la $k-1$ bolas elegidas con números menores que el de $B$ y pintarlos de rojo. Esto es posible sólo si $k\ge s$ en cuyo caso el número de $B$ es como máximo $2r-s+1$ y las bolas rojas tienen todas números en el conjunto $[2r-s]$ . Ahora tiramos las bolas con números que no están en $[2r-s]$ y pegar estrellas doradas en las bolas blancas que queden en el conjunto de bolas elegidas. En este punto tenemos $s-1$ bolas rojas y posiblemente algunas bolas blancas con estrellas doradas. Hay

$$\sum_k\binom{2r}{2k-1}\binom{k-1}{s-1}$$

posibles resultados.

• Comprueba que estos posibles resultados son exactamente los mismos que para la primera secuencia de operaciones.

Answer 2

Supongamos que buscamos verificar que $$\sum_{k=1}^r {2r\choose 2k-1} {k-1\choose s-1} = 2^{2r-2s+1} {2r-s\choose s-1}$$

donde presumiblemente $s\ge 1$ . El límite inferior se fija en $k=1$ ya que el primer coeficiente binomial es cero cuando $k=0.$

Introduzca $${2r\choose 2k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r-2k+2}} \frac{1}{(1-z)^{2k}} \; dz.$$

Esto proporciona un control del alcance y se desvanece cuando $k\gt r$ por lo que podemos extender el rango hasta el infinito, obteniendo

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \sum_{k\ge 1} {k-1\choose s-1} \frac{z^{2k}}{(1-z)^{2k}} \; dz.$$

Esto da como resultado

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \sum_{k\ge s} {k-1\choose s-1} \frac{z^{2k}}{(1-z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \frac{z^{2s}}{(1-z)^{2s}} \sum_{k\ge 0} {k+s-1\choose s-1} \frac{z^{2k}}{(1-z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \frac{z^{2s}}{(1-z)^{2s}} \frac{1}{(1-z^2/(1-z)^2)^s} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r-2s+2}} \frac{1}{((1-z)^2-z^2)^s} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r-2s+2}} \frac{1}{(1-2z)^s} \; dz.$$

Esto es

$$[z^{2r-2s+1}] \frac{1}{(1-2z)^s} = 2^{2r-2s+1} {2r-2s+1+s-1\choose s-1} \\ = 2^{2r-2s+1} {2r-s\choose s-1}$$

y tenemos la reclamación.

Answer 3

$$ \begin{align} \sum_k\binom{2r}{2k-1}\binom{k-1}{s-1} &=\sum_k\binom{2r}{2r-2k+1}\binom{k-1}{k-s}\tag1\\ &=\sum_k(-1)^{k-s}\binom{2r}{2r-2k+1}\binom{-s}{k-s}\tag2\\[3pt] &=\left[x^{2r-2s+1}\right](1+x)^{2r}\left(1-x^2\right)^{-s}\tag3\\[12pt] &=\left[x^{2r-2s+1}\right](1+x)^{2r-s}(1-x)^{-s}\tag4\\[9pt] &=\sum_k(-1)^k\binom{2r-s}{2r-2s-k+1}\binom{-s}{k}\tag5\\ &=\sum_k\binom{2r-s}{2r-2s-k+1}\binom{k+s-1}{k}\tag6\\ &=\sum_k\binom{2r-s}{k+s-1}\binom{k+s-1}{s-1}\tag7\\ &=\binom{2r-s}{s-1}\sum_k\binom{2r-2s+1}{k}\tag8\\ &=2^{2r-2s+1}\binom{2r-s}{s-1}\tag9 \end{align} $$ Explicación:
$(1)$ La simetría de El triángulo de Pascal
$(2)$ : aplicar coeficiente binomial negativo
$(3)$ : escribe la suma como el coeficiente en un producto
$(4)$ : anular los factores
$(5)$ : escribe el coeficiente de un producto como una suma
$(6)$ : aplicar el coeficiente binomial negativo
$(7)$ La simetría del triángulo de Pascal
$(8)$ : $\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$
$(9)$ : evalúa la suma