$\sum_{r=0}^n \binom{n}{r}2^{n-r}\binom{r}{[\frac{r}{2}]}$

Question

Solve the following summation. $$\sum_{r=0}^n \binom{n}{r}2^{n-r}\binom{r}{[\frac{r}{2}]} $$ where $[.]$ denotes the greatest integer function. I started by opening the series but everything is ok except GIF function, if I could handle it I believe I could be able to solve the problem. Please someone suggest a way to handle GIF.

Answer 1

Here is a starter. We can split the sum in even and odd part and obtain \begin{align*} \sum_{r=0}^n\binom{n}{r}2^{n-r}\binom{r}{\lceil\frac{r}{2}\rceil} &=\sum_{r\geq 0}^n\binom{n}{2r}2^{n-2r}\binom{2r}{r}\\ &\qquad+\sum_{r\geq 0}\binom{n}{2r+1}2^{n-2r-1}\binom{2r+1}{r+1}\tag{1} \end{align*}

Here we simplify the first sum of the right-hand side of (1) and show the following is valid \begin{align*} \color{blue}{\sum_{r\geq 0}\binom{n}{2r}2^{n-2r}\binom{2r}{r}=\binom{2n}{n}}\tag{2} \end{align*}

In order to prove (2) we use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k}\tag{3} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{r\geq 0}}&\color{blue}{\binom{n}{2r}2^{n-2r}\binom{2r}{r}}\\ &=\sum_{r\geq 0}\binom{n}{r}2^{n-2r}\binom{n-r}{n-2r}\tag{4}\\ &=\sum_{r\geq 0}\binom{n}{r}2^{n-2r}[z^{n-2r}](1+z)^{n-r}\tag{5}\\ &=2^n[z^n](1+z)^n\sum_{r\geq 0}\binom{n}{r}\left(\frac{z^2}{4(1+z)}\right)^r\tag{6}\\ &=2^n[z^n](1+z)^n\left(1+\frac{z^2}{4(1+z)}\right)^n\tag{7}\\ &=\frac{1}{2^n}[z^n]\left(4(1+z)+z^2\right)^n\\ &=\frac{1}{2^n}[z^n]\left(2+z\right)^{2n}\\ &\,\,\color{blue}{=\binom{2n}{n}}\tag{8} \end{align*} and the claim (2) follows.

Comment:

• in (4) we use the binomial identity \begin{align*} \binom{n}{2r}\binom{2r}{r}=\frac{n!}{(2r)!(n-2r)!}\,\frac{(2r)!}{r!r!}=\binom{n}{r}\binom{n-r}{n-2r} \end{align*}

• In (5) we apply (3).

• In (6) we do some rearrangements and use $[z^p]z^qA(z)=[z^{p-q}]A(z)$.

• In (7) we apply the binomial theorem.

• In (8) we select the coefficient of $z^n$.

Hint: The other sum can be similarly simplified and we get finally a nice closed formula for (1).

Answer 2

I agree with epi163sqrt that it is easier to consider odd and even $r$ separately. Here I provide a combinatorial proof of the identity $$\sum_{r \ge 0}\binom{n}{2r}2^{n - 2r}\binom{2r}{r} = \binom{2n}{n}.$$

As far as we know $\binom{2n}{n}$ is the number of ways to choose from a set of $2n$ elements a subset of $n$ elements. For simplicity we deal with numbers $\{\,1, 2, \ldots, 2n\,\}$. Consider it as $n$ pairs $$\{\,1, 2n\,\}, \{\,2, 2n - 1\,\}, \ldots, \{\,n, n + 1\,\}.$$ Out of these pairs we select $r$ pairs in which both numbers belong to our $n$ element subset. Then we have also $r$ pairs in which none of two numbers belongs to our $n$ element subset. And in each of the remaining $n - 2r$ pairs exactly one element belongs to our $n$ element subset, either the first or the second one.

Therefore there are $\binom{n}{r}$ ways to select pairs being subsets of $n$ element subset. Then there are $\binom{n - r}{r}$ ways to select pairs non-intersecting with the $n$ element subset. And there are $2^{n - 2r}$ ways to choose for each of the remaining pairs which of two elements belongs to the $n$ element subset. So $$\binom{2n}{n} = \sum_{r \ge 0}\binom{n}{r}\binom{n - r}{r}2^{n - 2r} = \sum_{r \ge 0}\binom{n}{2r}\binom{2r}{r}2^{n - 2r}.$$ The last equality holds because splitting $n$ pairs into three types can be done both as selecting $r$ pairs of the first type and the selecting $r$ pairs of the second type (what we have done), and as selecting $2r$ pairs of the first and second types together and then selecting $r$ pairs of the first type.

The similar idea works for the odd case if you choose from a set of $2n$ elements a subset of $n + 1$ elements. Also it is possible to combine both and choose from a set of $2n + 1$ elements a subset of $n$ elements. It gives you a full proof without explicit separation into cases.