Prove the identity:
$$\binom{n + 1}{a + b + 1} = \sum_{k = 0}^n \binom{k}{a}\binom{n – k}{b}$$
So far I understand the left side represents how many ways there are picking a+b+1 elements from a set (lets say X) with cardinality n+1. The right side as far as I understand means how many ways there are choosing a elements from a set with cardinality k and then number of ways choosing b elements from a set with n-k cardinality. However I do not see how adding all these sums as k goes from 0 to n adds up to the left hand side.
Thanks for the help.
(Side note: I wish to prove this without generating functions or Vandermondes identity, but with a counting argument).
Best Answer
The left side is how many ways to choose $a+b+1$ objects from $n+1$ objects.
We have to see why the right side is the same thing. Let $S=\{0, \ldots, n\}$, our set of $n+1$ objects. We want to count the number of ways to choose $C\subset S$ with $|C|=a+b+1$. Suppose that we will choose $C=\{n_0, \ldots, n_{a+b}\}$ with $n_0<\ldots <n_{a+b}$. We will choose in stages.
Stage $1$: Choose $n_a$. Let $k$ denote the value of $n_a$. Note that $0\leqslant k\leqslant n$.
Stage $2$: Choose $n_0, \ldots, n_{a-1}$ from $\{0, \ldots, k-1\}$. There are $\binom{k}{a}$ ways to do this.
Stage $3$: Choose $n_{a+1}, \ldots, n_{a+b}$ from $\{k+1, \ldots, n\}$. There are $\binom{n-k}{b}$ ways to do this.
Each $C\subset S$ arises in one and only one way from this sequence of choices, so the sum of all possible ways to choose in stages $1$-$3$, which is $\sum_{k=0}^n \binom{k}{a}\binom{n-k}{b}$, is equal to the number of ways to choose $C\subset S$ with $|C|=a+b+1$, which is $\binom{n+1}{a+b+1}$.