# Combinatorial proof of a binomial identity

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!

• Now that we have the accepted combinatorial proof if anyone is interested I can post an algebraic one as enrichment (very simple proof). – Marko Riedel Sep 7 '16 at 3:41
• Sure, @MarkoRiedel! I would like to see! – metricspace Sep 7 '16 at 3:50

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 $s\ge k$, 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.
• how could it be possible if you have $s\geq k$? Also, how did you get the bound on $B$? – metricspace Sep 7 '16 at 4:29
• @metricspace: If $s\ge k$, $\binom{k-1}{s-1}=0$, so the $k$ term is $0$: this case simply doesn’t get counted. As for the number on $B$, there are $k-1$ chosen balls with larger numbers, and $k\ge s$ (or the $k$ term is $0$ and doesn’t matter), so there are at least $s-1$ balls with larger numbers than $B$. That means that $B$’s number is at most $2r-(s-1)=2r-s+1$. – Brian M. Scott Sep 7 '16 at 5:35

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.