Combinatorial proof of a binomial identity: $\sum_k \binom {2r} {2k-1}\binom{k-1}{s-1} = 2^{2r-2s+1}\binom{2r-s}{s-1}$

Question

I am to find a combinatorial argument for the following identity:

$$\sum_k \binom {2r} {2k-1}\binom{k-1}{s-1} = 2^{2r-2s+1}\binom{2r-s}{s-1}$$

For the right hand side, I was think that would just be number of ways to choose at least $s-1$ elements out of a $[2r-s]$ set. However, for the left hand side, I don't really know what it is representing.

Any help would be greatly appreciated!

Answer 1

HINT: We have $2r-s$ white balls numbered $1$ through $2r-s$. We pick $s-1$ of them and paint those balls red, and we stick gold stars on any subset of the remaining white balls; since there are $2r-s-(s-1)=2r-2s+1$ white balls remaining, there are $$\binom{2r-s}{s-1}2^{2r-2s+1}$$ possible outcomes of this sequence of operations.

Alternatively, we can start with $2r$ white balls numbered $1$ through $2r$. We pick an odd number of these balls, $2k-1$ for some $k\in[r]$, and line them up in numerical order. The $k$-th ball in line is the one in the middle; call it $B$. We choose $s-1$ of the $k-1$ chosen balls with numbers smaller than that of $B$ and paint them red. This is possible only if $k\ge s$, in which case the number on $B$ is at most $2r-s+1$, and the red balls all have numbers in the set $[2r-s]$. We now throw away the balls with numbers not in $[2r-s]$ and stick gold stars on any white balls left in the set of chosen balls. At this point we have $s-1$ red balls and possibly some white balls with gold stars. There are

$$\sum_k\binom{2r}{2k-1}\binom{k-1}{s-1}$$

possible outcomes.

• Verify that these possible outcomes are exactly the same as for the first sequence of operations.

Answer 2

Suppose we seek to verify that $$\sum_{k=1}^r {2r\choose 2k-1} {k-1\choose s-1} = 2^{2r-2s+1} {2r-s\choose s-1}$$

where presumably $s\ge 1$. The lower limit is set to $k=1$ as the first binomial coefficient is zero when $k=0.$

Introduce $${2r\choose 2k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r-2k+2}} \frac{1}{(1-z)^{2k}} \; dz.$$

This provides range control and vanishes when $k\gt r$ so we may extend the range to infinity, obtaining

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \sum_{k\ge 1} {k-1\choose s-1} \frac{z^{2k}}{(1-z)^{2k}} \; dz.$$

This yields

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \sum_{k\ge s} {k-1\choose s-1} \frac{z^{2k}}{(1-z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \frac{z^{2s}}{(1-z)^{2s}} \sum_{k\ge 0} {k+s-1\choose s-1} \frac{z^{2k}}{(1-z)^{2k}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r+2}} \frac{z^{2s}}{(1-z)^{2s}} \frac{1}{(1-z^2/(1-z)^2)^s} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r-2s+2}} \frac{1}{((1-z)^2-z^2)^s} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2r-2s+2}} \frac{1}{(1-2z)^s} \; dz.$$

This is

$$[z^{2r-2s+1}] \frac{1}{(1-2z)^s} = 2^{2r-2s+1} {2r-2s+1+s-1\choose s-1} \\ = 2^{2r-2s+1} {2r-s\choose s-1}$$

and we have the claim.