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

score 1 · Accepted Answer · answered Oct 05 '18 at 08:41

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

answered Oct 05 '18 at 08:41

Bernard

175,478

Oh writing it out like that makes it so much more obvious/intuitive. Thanks! – Xiaomi Oct 05 '18 at 09:04

score 1 · Answer 2 · answered Oct 05 '18 at 09:01

1

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

answered Oct 05 '18 at 09:01

N. F. Taussig

76,571

1

Thanks this helped me understand it a lot better. Great example! – Xiaomi Oct 05 '18 at 09:04

Combinatorial formula in Binomial sum proof

2 Answers2