6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.