How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$

Question

Please help me to prove $\sum\limits_{i=0}^{\lfloor r/2\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$. By computer search I have found these for r varies from 0 to 10000. How to prove this for general $r\in N.$

Answer 1

Here is a proof based upon generating functions. It is convenient to use the coefficient of operator $[z^i]$ to denote the coefficient of $z^i$ in a series. This way we can write e.g. \begin{align*} [z^i](1+z)^n=\binom{n}{i} \end{align*}

We obtain \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*} and the claim follows.

Comment:

• In (1) we apply the coefficient of operator twice and set the upper limit of the sum to $\infty$ without changing anything, since we are adding zeros only.

• In (2) we use the linearity of the coefficient of operator, do some rearrangements and use the rule \begin{align*} [u^{p-q}]A(u)=[u^p]u^qA(u) \end{align*}

• In (3) we apply the substitution rule of the coefficient of operator with $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*}

• In (4) we do some simplifications.

• In (5) we select the coefficient of $u^r$.

Answer 2

Here's a combinatorial explanation using double-counting:

Imagine choosing a committee of $r$ people out of a group of $r$ men and $r$ women. The RHS counts that directly.

Alternatively, for a fixed $i$ with $0\leq i \leq \Big\lfloor\dfrac{r}{2}\Big\rfloor$, one could choose a committee containing at least $i$ men and at least $i$ women from the group of $r$ men and $r$ women in the following way. Save the women's seats in $\displaystyle \binom{r}{i}$ ways, then fill the men's positions in $\displaystyle \binom{r-i}{i}$ ways. Now that the requirement of at least $i$ men and at least $i$ women is fulfilled, each of the remaining $r-2i$ people have $2$ options - either they can join the committee or not and hence there are $2^{r-2i}$ ways of dealing with them.

Since these choices are independent, for a fixed $i$, there are $\displaystyle \binom{r}{i}\displaystyle \binom{r-i}{i}2^{r-2i}$ ways of choosing a committee containing at least $i$ men and at least $i$ women from a group of $r$ men and $r$ women.

Summing over $i=0 \ldots \Big\lfloor\dfrac{r}{2}\Big\rfloor$ covers all the possible minimum numbers of men and women in a committee selected from $r$ men and $r$ women.

Answer 3

Here is also a combinatorial proof, the idea slightly different, but basically the same as the one of @AryamanJal.

Suppose that you have a group of $r$ people and you want to do the do the following:

1) Choose a subgroup of $i\leqslant \lfloor\frac{r}{2}\rfloor$ people that we will call "distiguished", this gives $\binom{r}{i}$ possibilities.

2) Choose a subgroup of $r-2i$ among the remaining $r-i$ people who will be known as the "ones wearing hats", this gives $\binom{r-i}{r-2i}$ posibilities;

3) To every of the $r-2i$ people who should be wearing a hat you assign a blue or a red hat, this gives $2^{r-2i}$ possibilities.

The remaining $r-i-(r-2i)=i$ people will be "normal".

The total number of possibilities to do this for any such $i$ is precisely the quantity on the LHS.

You can also count it in another way. Make $2r$ labels, $r$ of them blue and $r$ of them red, so that each person has his name on exatly one red label and exactly one blue label. Then, you randomly choose $r$ of the $2r$ unique labels, there are $\binom{2r}{r}$ ways to make this choice.

If a person's name is picked twice, they shall be distinguished. If the name is picked only once, they shall wear the hat of the respective color. If their name is not picked, a person will remain normal.