# Combinatorial identity involving binomial coefficients

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?

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