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.

Solution 1:

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.

Solution 2:

$\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.} $$