How to prove the binomial identity $\binom{n + 1}{a + b + 1} = \sum_{k = 0}^n \binom{k}{a}\binom{n - k}{b}$ 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).
 A: 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}$.
A: 
An algebraic approach. We obtain
\begin{align*}
\color{blue}{\sum_{k=0}^n\binom{k}{a}\binom{n-k}{b}}
&=\sum_{k=a}^{n-b}\binom{k}{a}\binom{n-k}{b}\tag{1}\\
&=\sum_{k=0}^{n-a-b}\binom{k+a}{a}\binom{n-a-k}{b}\tag{2}\\
&=\sum_{k=0}^{n-a-b}\binom{k+a}{k}\binom{n-a-k}{n-a-b-k}\tag{3}\\
&=\sum_{k=0}^{n-a-b}\binom{-a-1}{k}\binom{-b-1}{n-a-b-k}(-1)^{n-a-b}\tag{4}\\
&=\binom{-a-b-2}{n-a-b}(-1)^{n-a-b}\tag{5}\\
&=\binom{n+1}{n-a-b}\tag{6}\\
&\,\,\color{blue}{=\binom{n+1}{a+b+1}}\tag{7}
\end{align*}
and the claim follows.

Comment:

*

*In (1) we restrict lower and upper index respecting that $\binom{p}{q}=0$ if $p<q$.


*In (2) we shift the index to start with $k=0$.


*In (3) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.


*In (4) we use $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.


*In (5) we apply the Vandermonde's identity.


*In (6) we use $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ as in (3).


*In (7) we use $\binom{p}{q}=\binom{p}{p-q}$ as in (4).
A: The summand represents the number of ways to choose $a+b+1$ numbers from $1,...,n+1$ such that the $(a+1)$-th smallest number equals $k$.
When you add for all possible $k$, you get the total number of ways to choose $a+b+1$ from $n+1$ which is the LHS.
