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

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

\begin{align} \sum_k\binom{2r}{2k-1}\binom{k-1}{s-1} &=\sum_k\binom{2r}{2r-2k+1}\binom{k-1}{k-s}\tag1\\ &=\sum_k(-1)^{k-s}\binom{2r}{2r-2k+1}\binom{-s}{k-s}\tag2\\[3pt] &=\left[x^{2r-2s+1}\right](1+x)^{2r}\left(1-x^2\right)^{-s}\tag3\\[12pt] &=\left[x^{2r-2s+1}\right](1+x)^{2r-s}(1-x)^{-s}\tag4\\[9pt] &=\sum_k(-1)^k\binom{2r-s}{2r-2s-k+1}\binom{-s}{k}\tag5\\ &=\sum_k\binom{2r-s}{2r-2s-k+1}\binom{k+s-1}{k}\tag6\\ &=\sum_k\binom{2r-s}{k+s-1}\binom{k+s-1}{s-1}\tag7\\ &=\binom{2r-s}{s-1}\sum_k\binom{2r-2s+1}{k}\tag8\\ &=2^{2r-2s+1}\binom{2r-s}{s-1}\tag9 \end{align} Explanation:
$$(1)$$: symmetry of Pascal's triangle
$$(2)$$: apply negative binomial coefficient
$$(3)$$: write the sum as the coefficient in a product
$$(4)$$: cancel factors
$$(5)$$: write the coefficient in a product as a sum
$$(6)$$: apply negative binomial coefficient
$$(7)$$: symmetry of Pascal's triangle
$$(8)$$: $$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$$
$$(9)$$: evaluate the sum

• +1 for a nice and clean proof! :) – Brahadeesh Sep 13 '19 at 15:16
• @Brahadeesh: I am working on turning steps $(3)$ and $(4)$ into a combinatorial argument. If it is significantly different from Brian Scott's, I will amend my answer. – robjohn Sep 13 '19 at 15:33
• Do ping me if you succeed, I'd love to see such an argument :) – Brahadeesh Sep 13 '19 at 15:38