Show that $ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $?

Question

I can't resolve this exercise and I need a tip.

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

where $ n \geq s $.

Answer 1

Apply the following in order:

• symmetry to get the summation index $k$ to appear at the bottom

• upper negation to remove $k$ from the top

• Vandermonde's identity to settle the summation and remove $k$

• upper negation to make $r, s$ appear at the top

• symmetry to remove $r, s$ from the bottom.

Answer 2

Let's count in how many ways one can choose $m+n+1$ numbers $a_1<a_2<\cdots <a_{m+n+1}$ out of $\{1,2,\cdots, r+s+1\}$?

Since $n\ge s$, one can only choose $a_{n+1}$ from $\{s+1,\cdots, s+r+1\}$. For each value $a_{n+1}=s+k+1$, one then continue to choose $a_1<a_2<\cdots<a_n\leq s+k$ and...

Answer 3

Suppose we seek to evaluate $$\sum_{k=0}^r {r-k\choose m} {s+k\choose n}$$ where $n\ge s$ and $m\le r.$

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

Note that this is zero when $k\gt r-m$ so we may extend the sum in $k$ to $k=\infty.$

Introduce furthermore $${s+k\choose n} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{s+k}}{w^{n+1}} \; dw.$$

This yields for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-m+1}} \frac{1}{(1-z)^{m+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{s}}{w^{n+1}} \sum_{k\ge 0} z^k (1+w)^k \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-m+1}} \frac{1}{(1-z)^{m+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{s}}{w^{n+1}} \frac{1}{1-(1+w)z} \; dw\; dz.$$

For the geometric series to converge we must have $|z(1+w)|\lt 1$, which also ensures that the inner pole is not inside the contour. Observe that $|z(1+w)| = \epsilon |1+w| \le \epsilon (1+\gamma).$ So we need to choose $1+\gamma \lt 1/\epsilon$ with $\epsilon$ in a neighborhood of zero. The choice $\epsilon=1/2$ and $\gamma=1/2$ will work.

Continuing we find $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-m+1}} \frac{1}{(1-z)^{m+2}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(1+w)^{s}}{w^{n+1}} \frac{1}{1-wz/(1-z)} \; dw\; dz.$$

Extracting the inner residue we get $$\sum_{q=0}^n {s\choose n-q} \frac{z^q}{(1-z)^q}.$$

Now $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{r-m-q+1}} \frac{1}{(1-z)^{m+q+2}} \; dz = {r+1\choose m+q+1}$$

which yields for the sum $$\sum_{q=0}^n {s\choose n-q} {r+1\choose m+q+1}.$$

Continue by re-indexing for $$\sum_{q=0}^s {s\choose q} {r+1\choose m+n-q+1}$$

where we have lowered the upper limit to $s$ since the first binomial coefficient is zero when $q\gt s.$

Using $${r+1\choose m+n-q+1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{r+1}}{z^{m+n-q+2}} dz$$

we thus obtain for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{r+1}}{z^{m+n+2}} \sum_{q=0}^s {s\choose q} z^q dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{r+s+1}}{z^{m+n+2}} = {s+r+1\choose n+m+1}.$$

Remark. This can be done using formal power series only.

We have for the sum

$$\sum_{k=0}^r {r-k\choose m} {s+k\choose n} = \sum_{k=0}^r [z^{r-k-m}] \frac{1}{(1-z)^{m+1}} [w^n] (1+w)^{s+k} \\ = [z^{r-m}] \frac{1}{(1-z)^{m+1}} [w^n] (1+w)^{s} \sum_{k=0}^r z^k (1+w)^k.$$

Now we may certainly extend the sum to infinity as there is no contribution to the coefficient extractor when $k\gt r-m$ (recall that $r\ge m$) getting

$$[z^{r-m}] \frac{1}{(1-z)^{m+1}} [w^n] (1+w)^{s} \sum_{k\ge 0} z^k (1+w)^k \\ = [z^{r-m}] \frac{1}{(1-z)^{m+1}} [w^n] (1+w)^{s} \frac{1}{1-z(1+w)} \\ = [z^{r-m}] \frac{1}{(1-z)^{m+1}} [w^n] (1+w)^{s} \frac{1}{1-z-wz} \\ = [z^{r-m}] \frac{1}{(1-z)^{m+2}} [w^n] (1+w)^{s} \frac{1}{1-wz/(1-z)}.$$

Now with $n\ge s$ we get for the inner coefficient

$$\sum_{q=0}^s {s\choose q} \frac{z^{n-q}}{(1-z)^{n-q}}.$$

Substitute into the outer coefficient extractor to get

$$[z^{r-m}] \frac{1}{(1-z)^{m+2}} \sum_{q=0}^s {s\choose q} \frac{z^{n-q}}{(1-z)^{n-q}} = [z^{r-m}] \sum_{q=0}^s {s\choose q} \frac{z^{n-q}}{(1-z)^{n+m+2-q}} \\ = \sum_{q=0}^s {s\choose q} [z^{r-m-n+q}] \frac{1}{(1-z)^{n+m+2-q}} = \sum_{q=0}^s {s\choose q} {r+1\choose n+m+1-q} \\ = \sum_{q=0}^s {s\choose q} [z^{n+m+1-q}] (1+z)^{r+1} = [z^{n+m+1}] (1+z)^{r+1} \sum_{q=0}^s {s\choose q} z^q \\ = [z^{n+m+1}] (1+z)^{r+1} (1+z)^s = [z^{n+m+1}] (1+z)^{r+s+1} = {r+s+1\choose n+m+1}.$$