Proving $\sum_{k=0}^{n} {k \choose a} {n-k \choose b} = {n+1\choose a+b+1}$ 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.
 A: 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.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{\sum_{k\ =\ 0}^{n}{k \choose a}{n - k \choose b}={n + 1 \choose a + b +1}:
     \ {\large ?}}$.

$$\mbox{Lets}\quad
{\cal F}\pars{z} \equiv \sum_{n\ =\ 0}^{\infty}\bracks{%
\sum_{k\ =\ 0}^{n}{k \choose a}{n - k \choose b}}z^{n}\tag{1}
$$

such that
\begin{align}{\cal F}\pars{z}&
=\sum_{k\ =\ 0}^{\infty}{k \choose a}\sum_{n\ =\ k}^{\infty}{n - k \choose b}z^{n}
=\sum_{k\ =\ 0}^{\infty}{k \choose a}\sum_{n\ =\ 0}^{\infty}{n \choose b}z^{n + k}
\\[5mm]&=\bracks{\sum_{k\ =\ 0}^{\infty}{k \choose a}z^{k}}
\bracks{\sum_{n\ =\ 0}^{\infty}{n \choose b}z^{n}}
\end{align}

So, we have to evaluate the following sum:
  \begin{align}
\sum_{j\ =\ 0}^{\infty}{j \choose c}z^{j}&=
\sum_{j\ =\ 0}^{\infty}
\bracks{\oint_{\verts{w}\ =\ a}{\pars{1 + w}^{j} \over w^{c + 1}}
\,{\dd w \over 2\pi\ic}}z^{j}
\\[5mm] & =\oint_{\verts{w}\ =\ a}
{1 \over w^{c + 1}}\sum_{j\ =\ 0}^{\infty}\bracks{\pars{1 + w}z}^{j}
\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{w}\ =\ a}{1 \over w^{c + 1}}{1 \over 1 - \pars{1 + w}z}
\,{\dd w \over 2\pi\ic}
\\[5mm]&={1 \over z\pars{1/z - 1}}\oint_{\verts{w}\ =\ a}{1 \over w^{c + 1}}{1 \over 1 - w/\pars{1/z - 1}}
\,{\dd z \over 2\pi\ic}
\\[5mm]&={1 \over z\pars{1/z - 1}}\sum_{j\ =\ 0}^{\infty}\pars{1/z - 1}^{-j}
\oint_{\verts{w}\ =\ a}{1 \over w^{c - j + 1}}\,{\dd z \over 2\pi\ic}
\\[5mm] & =
{1 \over z\pars{1/z - 1}^{c + 1}}
\end{align}
  Note that we can choose $\ds{0\ <\ a}$ such that
  $\ds{\verts{\pars{1 + w}z}\ <\ 1}$

Then,
\begin{align}
{\cal F}\pars{z}&={1 \over z\pars{1/z - 1}^{a + 1}}\,
{1 \over z\pars{1/z - 1}^{b + 1}}={z^{a + b} \over \pars{1 - z}^{a + b + 2}}
\\[5mm] & =
z^{a + b}\sum_{n\ =\ 0}^{\infty}
{-a - b - 2 \choose n}\pars{-1}^{n}z^{n}
\\[5mm]&=\sum_{n\ =\ a + b}^{\infty}{-a - b - 2 \choose n - a - b}
\pars{-1}^{n - a - b}z^{n}
\\[5mm]&=\sum_{n\ =\ a + b}^{\infty}
{a + b + 2 + n - a - b - 1\choose n - a - b}\pars{-1}^{n - a - b}
\pars{-1}^{n - a - b}z^{n}
\\[5mm]&=\sum_{n\ =\ a + b}^{\infty}{n + 1 \choose n - a - b}z^{n}
=\sum_{n\ =\ a + b}^{\infty}\color{#66f}{\large{n + 1 \choose a + b + 1}}z^{n}
\qquad\qquad\qquad\qquad\qquad\pars{2}
\end{align}

With $\pars{1}$ and $\pars{2}$ we conclude:
  $$\color{#66f}{\large%
\sum_{k\ =\ 0}^{n}{k \choose a}{n - k \choose b}
=\left\{\begin{array}{lcl}
{n + 1 \choose a + b + 1} & \mbox{if} & n\ \geq a + b
\\[2mm]
0 &&\mbox{otherwise}
\end{array}\right.}
$$

A: We proved at the following
MSE link
that
$$\sum_{q=a+1}^n {q-1\choose a} {n-q\choose k-a}
= {n\choose k+1}$$
where $k\ge a$ for the binomial coefficient to be defined,
and $n\ge a+1$ or alternatively
$$\sum_{q=a}^{n-1} {q\choose a} {n-1-q\choose k-a}
= {n\choose k+1}$$
Now putting $n := n+1$ and $k=a+b$ we obtain (since $k\ge a$ and $a\ge
0$ we must have $k=a+b$ with $b$ non-negative)
$$\sum_{q=a}^{n} {q\choose a} {n-q\choose b}
= {n+1\choose a+b+1}.$$
Owing to the first binomial coefficient this becomes
$$\sum_{q=0}^{n} {q\choose a} {n-q\choose b}
= {n+1\choose a+b+1}.$$
which is the claim.
