8
$\begingroup$

I want to show that the following holds:

$$\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}.$$

I have an idea of what is going on here. On the RHS we are selecting $r+s+1$ elements from the set $[m+n+1]$. Another way of doing this is to partition the set $[m+n+1]$ into two sets in several ways by shifting $k$ elements from one set to the other. For example, we can partition $[m+n+1]$ into a set with $m+k$ elements and a set with $n+1-k$ elements. From the set with $m+k$ elements we can select $r$ elements and from the set with $n+1-k$ elements we can select $s+1$. However, this is not matching the LHS. I believe the problem is that we don't know which $k$ elements are being shifted around.

I thought rewriting the sum as follows would help:

$$\sum_{k=0}^{m+n} \binom{k}{r} \binom{n+m-k}{s}.$$

I just don't understand why the "$+1$" on the top and bottom of the RHS disappear. I have spent several hours on this problem, and I have run out of ideas. Please help, I truly appreciate it.

$\endgroup$
0
$\begingroup$

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

\begin{equation} \sum_{k = -m}^{n}{m + k \choose r}{n - k \choose s} = {m + n + 1 \choose r + s + 1}:\ {\large ?} \label{1}\tag{1} \end{equation} LHS variables must satisfy $\left\{\begin{array}{rcl} \ds{m + k \geq r \geq 0} & \ds{\implies} & \left\{\begin{array}{l} \ds{r \geq 0 } \\[2mm] \ds{k \geq r - m \geq -m} \end{array}\right. \\[1mm] \ds{n - k \geq s \geq 0} & \ds{\implies} & \left\{\begin{array}{l} \ds{s \geq 0 } \\[2mm] \ds{k \leq n - s \leq n} \end{array}\right. \end{array}\right.$


Then, \begin{align} &\color{#f00}{\sum_{k = -m}^{n}{m + k \choose r}{n - k \choose s}} = \sum_{k = r - m}^{n - s}{m + k \choose r}{n - k \choose s} = \sum_{k = r - m}^{\infty}{m + k \choose r}{n - k \choose s} \\[5mm] = &\ \sum_{k = 0}^{\infty}{m + \pars{k + r - m} \choose r} {n - \pars{k + r - m} \choose s} = \sum_{k = 0}^{\infty}{k + r \choose k} {m + n - r - k \choose m + n - r - k - s} \\[5mm] = &\ \sum_{k = 0}^{\infty}{-r - 1 \choose k}\pars{-1}^{k} {-s - 1 \choose m + n - r - s - k}\pars{-1}^{m + n - r - s - k} \\[5mm] = &\ \pars{-1}^{m + n + r + s}\sum_{k = 0}^{\infty}{-r - 1 \choose k} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1} \over z^{m + n - r - s - k + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{m + n + r + s} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1} \over z^{m + n - r - s + 1}} \sum_{k = 0}^{\infty}{-r - 1 \choose k}z^{k}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{m + n + r + s} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1} \over z^{m + n - r - s + 1}} \pars{1 + z}^{-r - 1}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{m + n + r + s} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-s - 1 - r - 1} \over z^{m + n - r - s + 1}}\,{\dd z \over 2\pi\ic} = \pars{-1}^{m + n + r + s}{-s - r - 2 \choose m + n - r - s} \\[5mm] = &\ \pars{-1}^{m + n + r + s}{s + r + 2 + m + n - r - s - 1 \choose m + n - r - s} \pars{-1}^{m + n - r - s} \\[5mm] = &\ {m + n + 1 \choose m + n - r - s} = {m + n + 1 \choose \bracks{m + n + 1} - \bracks{m + n - r - s}} = \color{#f00}{m + n + 1 \choose r + s + 1} \end{align}

$\endgroup$
0
$\begingroup$

Suppose we seek to evaluate

$$\sum_{k=-m}^n {m+k\choose r} {n-k\choose s} = \sum_{k=0}^{m+n} {k\choose r} {m+n-k\choose s}.$$

Here we may assume that $r$ and $s$ are non-negative. We introduce

$${m+n-k\choose s} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+n-k-s+1}} \frac{1}{(1-z)^{s+1}} \; dz.$$

This integral controls the range, being zero when $k\gt m+n$ and we may extend the range of $k$ to infinity. We get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+n-s+1}} \frac{1}{(1-z)^{s+1}} \sum_{k\ge 0} {k\choose r} z^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+n-s+1}} \frac{1}{(1-z)^{s+1}} \sum_{k\ge r} {k\choose r} z^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+n-s+1}} \frac{z^r}{(1-z)^{s+1}} \sum_{k\ge 0} {k+r\choose r} z^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+n-s+1}} \frac{z^r}{(1-z)^{s+1}} \frac{1}{(1-z)^{r+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+n-r-s+1}} \frac{1}{(1-z)^{r+s+2}} \; dz.$$

We get for the answer

$${m+n-r-s+r+s+1\choose r+s+1} = {m+n+1\choose r+s+1}.$$

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