Csdrhrt

Given two positive integers $a$ and $b$, prove that

$sum_{k=0}^{n} {k choose a} {n-k choose b} = {n+1choose 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.

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.

$newcommand{angles}[1]{leftlangle, #1 ,rightrangle}
newcommand{braces}[1]{leftlbrace, #1 ,rightrbrace}
newcommand{bracks}[1]{leftlbrack, #1 ,rightrbrack}
newcommand{ceil}[1]{,leftlceil, #1 ,rightrceil,}
newcommand{dd}{{rm d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,{rm e}^{#1},}
newcommand{fermi}{,{rm f}}
newcommand{floor}[1]{,leftlfloor #1 rightrfloor,}
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]{leftvert, #1 ,rightvert}$
$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 2piic}}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 2piic}
\[5mm]&=oint_{verts{w} = a}{1 over w^{c + 1}}{1 over 1 - pars{1 + w}z}
,{dd w over 2piic}
\[5mm]&={1 over zpars{1/z - 1}}oint_{verts{w} = a}{1 over w^{c + 1}}{1 over 1 - w/pars{1/z - 1}}
,{dd z over 2piic}
\[5mm]&={1 over zpars{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 2piic}
\[5mm] & =
{1 over zpars{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 zpars{1/z - 1}^{a + 1}},
{1 over zpars{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 - 1choose 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}
qquadqquadqquadqquadqquadpars{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.}
$$