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}$

Solution 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$.

Solution 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.