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}$ 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.$ 
 A: 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$.
A: 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.  
A: 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. 
