Combinatorial formula in Binomial sum proof

Question

To show that the sum of independent binomial r.v $X$ and $Y$ with common probability $p$ is also a binomial random variable I need to show

$$\sum_{k=0}^z {n \choose k}{m \choose z-k}={m+n \choose z}$$

I've tried writing this out in factorials but I can't seem to get anywhere. Further I can't see how we can get an $(m+n)!$ out of the product of $(z+1) \times n! m!$. I think there must be a specific combination property of formula I can use here.

Any hints/advice would be appreciated

Answer 1

Hint:

That is Vandermonde's identity. To prove it, compare the coefficients of $x^z$ in the expansions of both sides of the equality $$(1+x)^m(1+x)^n=(1+x)^{m+n}.$$

Answer 2

The right hand side counts the number of ways of selecting $z$ people from $m$ men and $n$ women. The left hand side counts the same thing since if we select exactly $k$ women, we must select $z - k$ men, where $0 \leq k \leq z$.