Given two positive integers $a$ and $b$, prove that
$\sum_{k=0}^{n} {k \choose a} {n-k \choose b} = {n+1\choose a+b+1}$
I think there should be a good combinatorial proof for this, given the simplicity of the right-hand side… my hunch is to form all possible subsets of size $a+b+1$ by dividing the set into $k$ and $n-k$ elements, then choosing $a$ from the first, $b$ from the second, iterating over all values of $k$.
I can't quite make this work, so I've also been trying to rewrite ${n+1 \choose a+b+1}$ to make it clear.
Open to any proof method, all help appreciated.
Best Answer
HINT: Let $M=\{0,1,\ldots,n\}$; the righthand side is the number of subsets of $M$ of size $a+b+1$. If $S=\{m_0^S,\ldots,m_{a+b}^S\}$ is such a subset, indexed in increasing order, $S$ has $a$ members that are smaller than $m_a^S$ and $b$ members that are larger than $m_a^S$. Classify the sets $S$ according to the value of $m_a^S$ to see where the lefthand side comes from.