1
$\begingroup$

I am trying to prove the following identity:

$$ \sum_{n=k}^{s-r} \binom{n}{k} \binom{s-n}{r} = \binom{s + 1}{k + r + 1} $$

It looks kind of like a flipped version of Vandermonde's identity but I haven't been able to make any progress in proving it. I've verified it for random small values of $k, r$ and $s$ using a computer.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Suppose that you have a row $s+1$ balls, and you want to choose $k+r+1$ of them; clearly that can be done in $\binom{s+1}{k+r+1}$ ways.

Now we’ll break that down according to the position of the $(k+1)$-st of the chosen balls. There must be at least $k$ balls to the left of it, so the first position in which it could possibly occur is position $k+1$. There must be at least $r$ balls to right of it, so the last position in which it could occur is position $s+1-r$. Thus, number of balls to the left of it must be at least $k$ and at most $s-r$.

Let $n$ be the number of balls to the left of it, so that $n$ ranges from $k$ through $s-r$. The $k$ chosen balls that precede it can be any $k$ of the $n$ balls to its left, so there are $\binom{n}k$ ways to choose them. The $r$ chosen balls that follow it can be any of the $s-n$ balls to its right, so there are $\binom{s-n}r$ of them. Thus, there are $\binom{n}k\binom{s-n}r$ ways to choose the $k+r+1$ balls so that there are $n$ balls to the left of the $(k+1)$-st chosen ball. Summing over the possible values of $n$ will give us the total number of ways to choose $k+r+1$ balls, so

$$\sum_{n=k}^{s-r}\binom{n}k\binom{s-n}r=\binom{s+1}{k+r+1}\;.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .