Show that the hypergeometric distribution add to unity.

Question

(Feller Volume 1, 2.12.8) In section 6 we remarked that the terms of the hypergeometric distribution should add to unity. This amounts to saying that for any positive integers $a, b, n,$ $${a \choose 0}{b \choose n} + {a \choose 1}{b \choose n-1} + ... + {a \choose n}{b \choose 0} = {a+b \choose n}.$$

Prove this by induction. Hint: Prove first that the equation holds for $a=1$ and all $b$.

For $a=1$, ${1 \choose 0}{b \choose n} + {1 \choose 1}{b \choose n-1} = {b \choose n} + {b \choose n-1} = {b+1 \choose n} $. Assuming that the case for $a =k$ is true, consider the case for $a= k+1$. I found that $$\sum_{j=0}^n {k+1 \choose j}{b \choose n-j} = \sum_{j=0}^n \frac{k+1}{k+1-j}{k \choose j}{b \choose n-j}.$$ But still $\frac{k+1}{k+1-j}$ depends on $j$, which make me unable to use the induction hypothesis. Could you give me some suggestion?

Answer 1

\begin{align} \sum_{j=0}^{n} {k+1 \choose j}{b \choose n-j} &= \sum_{j=0}^{n-1} {k \choose j}{b \choose n-j-1}+\binom{b+k}{n} \\ &=\binom{b+k}{n-1}+\binom{b+k}{n}=\binom{b+k+1}{n}. \end{align}