0
$\begingroup$

Prove for $n, r, s \geq 0$ $$ \sum_{i=0}^n \binom{n}{r} \binom{r}{i} \binom{n-r}{s-i} = \binom{n}{r} \binom{n}{s}$$

My first idea was since the $\binom{n}{r}$ term can be taken out of the sum, perhaps we can eliminate the term on both sides of the equation, leaving us with $$ \sum_{i=0}^n \binom{r}{i} \binom{n-r}{s-i} = \binom{n}{s}$$

But even then I'm at a loss, the only identity involving sums and binomial coefficients I know is $ \displaystyle \sum_{k=0}^n {n \choose k} = 2^n$, which I don't see being useful here. Any hints?

$\endgroup$
1
$\begingroup$

Notice the $\binom{n}{s}$ is the number of subsets of $[n]$ of size $s$.

$\binom{r}{i}$ is the number of subsets of $[r]$ of size $i$ and $\binom{n-r}{s-i}$ is the number of subsets of $[n]\setminus [r]$ of size $s-i$. Since the union of a subset of $[r]$ of size $i$ and a subset of $[n]\setminus[r]$ of size $s-i$ is a subset of $[n]$ of size $s$, we know that $\binom{r}{i}\binom{n-r}{s-i}$ is the number of subsets of $[n]$ of size $s$ with $i$ elements in $[r]$ and $s-i$ elements in $[n]\setminus [r]$. Summing up over all $i$, we obtain the total possible number of subsets of $[n]$ of size $s$, so $$\sum_{i=1}^n\binom{r}{i}\binom{n-r}{s-i}=\binom{n}{s}$$

$\endgroup$

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.