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!

  • $\begingroup$ Now that we have the accepted combinatorial proof if anyone is interested I can post an algebraic one as enrichment (very simple proof). $\endgroup$ – Marko Riedel Sep 7 '16 at 3:41
  • $\begingroup$ Sure, @MarkoRiedel! I would like to see! $\endgroup$ – 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


possible outcomes.

  • Verify that these possible outcomes are exactly the same as for the first sequence of operations.
  • $\begingroup$ how could it be possible if you have $s\geq k$? Also, how did you get the bound on $B$? $\endgroup$ – metricspace Sep 7 '16 at 4:29
  • $\begingroup$ @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$. $\endgroup$ – 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

  • $\begingroup$ +1 for a nice and clean proof! :) $\endgroup$ – Brahadeesh Sep 13 '19 at 15:16
  • 1
    $\begingroup$ @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. $\endgroup$ – robjohn Sep 13 '19 at 15:33
  • $\begingroup$ Do ping me if you succeed, I'd love to see such an argument :) $\endgroup$ – Brahadeesh Sep 13 '19 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.