Cómo probar$\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$

Question

Por favor, ayúdame a probar$\sum\limits_{i=0}^{\lfloor r/2\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$. Por la búsqueda de la computadora he encontrado estos para r varía de 0 a 10000. ¿Cómo probar esto para general$r\in N.$

Answer 1

Aquí es una prueba basada en la generación de funciones. Es conveniente utilizar el coeficiente de operador $[z^i]$ para denotar el coeficiente de $z^i$ en una serie. De esta manera podemos escribir por ejemplo \begin{align*} [z^i](1+z)^n=\binom{n}{i} \end{align*}

Obtenemos \begin{align*} \color{blue}{\sum_{i=0}^{\lfloor r/2\rfloor}}&\color{blue}{\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}}\\ &=\sum_{i=0}^\infty[z^{i}](1+z)^{r}[u^{r-2i}](1+2u)^{r-i}\tag{1}\\ &=[u^r](1+2u)^r\sum_{i=0}^\infty\left(\frac{u^2}{1+2u}\right)^i[z^i](1+z)^r\tag{2}\\ &=[u^r](1+2u)^r\left(1+\frac{u^2}{1+2u}\right)^r\tag{3}\\ &=[u^r](1+u)^{2r}\tag{4}\\ &\color{blue}{=\binom{2r}{r}}\tag{5} \end{align*} y el reclamo de la siguiente manera.

Comentario:

• En (1) se aplica el coeficiente de operador dos veces y establecer el límite superior de la suma a $\infty$ sin cambiar nada, ya que estamos añadiendo ceros sólo.

• En (2) utilizamos la linealidad del coeficiente de operador, hacer algunos cambios y el uso de la regla \begin{align*} [u^{p-q}]A(u)=[u^p]u^qA(u) \end{align*}

• En (3) se aplica la norma de sustitución del coeficiente de operador con $z:=\frac{u^2}{1+2u}$ \begin{align*} A(u)=\sum_{i=0}^\infty a_i u^i=\sum_{i=0}^\infty u^i [z^i]A(z) \end{align*}

• En (4) vamos a hacer algunas simplificaciones.

• En (5) se selecciona el coeficiente de $u^r$.

Answer 2

Aquí está una combinatoria explicación utilizando la doble contabilización:

Imaginar la elección de un comité de $r$ de personas de un grupo de $r$ hombres y $r$ mujeres. El RHS cuenta que directamente.

Alternativamente, para una fija $i$$0\leq i \leq \Big\lfloor\dfrac{r}{2}\Big\rfloor$, uno podría elegir un comité que contenga, al menos, $i$ de los hombres y, al menos, $i$ de las mujeres del grupo de $r$ hombres y $r$ de las mujeres de la siguiente manera. Salvar a la mujer asientos en $\displaystyle \binom{r}{i}$ maneras, a continuación, rellenar los hombres posiciones en $\displaystyle \binom{r-i}{i}$ maneras. Ahora que el requisito de al menos $i$ de los hombres y, al menos, $i$ de las mujeres se ha cumplido, cada uno de los restantes $r-2i$ de las personas tienen $2$ opciones - o pueden unirse a la comisión o no y por lo tanto no se $2^{r-2i}$ maneras de lidiar con ellos.

Dado que estas decisiones son independientes, por un determinado $i$, $\displaystyle \binom{r}{i}\displaystyle \binom{r-i}{i}2^{r-2i}$ maneras de elegir un comité que contenga, al menos, $i$ de los hombres y, al menos, $i$ mujeres de un grupo de $r$ hombres y $r$ mujeres.

Suma más de $i=0 \ldots \Big\lfloor\dfrac{r}{2}\Big\rfloor$ cubre todos los posibles mínimo número de hombres y mujeres en un comité seleccionado de $r$ hombres y $r$ mujeres.

Answer 3

Aquí es también una combinatoria de la prueba, la idea ligeramente diferente, pero básicamente la misma que la de @AryamanJal.

Supongamos que usted tiene un grupo de $r$ personas y quiere hacer el hacer lo siguiente:

1) Elegir un subgrupo de $i\leqslant \lfloor\frac{r}{2}\rfloor$ de la gente que vamos a llamar "distiguished", esto da $\binom{r}{i}$ posibilidades.

2) Elegir un subgrupo de $r-2i$ entre el resto de los $r-i$ de las personas que serán conocidos como los "sombreros", esto da $\binom{r-i}{r-2i}$ posibilidades;

3) Para cada una de las $r-2i$ de las personas que deben usar un sombrero de asignar un azul o un sombrero rojo, esto da $2^{r-2i}$ posibilidades.

El resto de los $r-i-(r-2i)=i$ gente va a ser "normal".

El número total de posibilidades para hacer esto para cualquier $i$ es precisamente la cantidad en el lado izquierdo.

También puede contar de otra manera. Hacer $2r$ etiquetas, $r$ azul y $r$ rojo, de modo que cada persona tiene su nombre en exatly una etiqueta roja y exactamente una etiqueta azul. A continuación, elija aleatoriamente $r$ de la $2r$ etiquetas exclusivas, hay $\binom{2r}{r}$ maneras de hacer esta elección.

Si el nombre de una persona es elegida dos veces, serán distinguidos. Si el nombre es recogido sólo una vez, deberán llevar el sombrero de los respectivos colores. Si su nombre no está recogido, una persona permanecerá normal.