A combinatorial sum via generating series?

Question

I would like to prove that $$\sum_{k=0}^{n} {k \choose m} {n-k \choose r-m} = {n+1 \choose r+1}$$ holds for all $n \in \mathbb{N}$ and $0 \leq m < r \leq \frac{n}{2}$. It seems that you may be able to use generating functions, with the Cauchy product, but I am not really sure on the details. I would like an algebraic proof of this.

Answer 1

We seek to verify that

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

where $n\ge 0$ and $0\le m \le n$ and $m\le r\le n.$

We get for the LHS

$$\begin{align*} & [z^m] [w^{r-m}] \sum_{k=0}^n (1+z)^k (1+w)^{n-k} \\ & = [z^m] [w^{r-m}] (1+w)^n \sum_{k=0}^n (1+z)^k (1+w)^{-k} \\ & = [z^m] [w^{r-m}] (1+w)^n \frac{(1+z)^{n+1}/(1+w)^{n+1}-1}{(1+z)/(1+w)-1} \\ & = [z^m] [w^{r-m}] (1+w)^n \frac{(1+z)^{n+1}/(1+w)^{n}-(1+w)}{z-w} \\ & = [z^m] [w^{r-m}] \frac{(1+z)^{n+1}-(1+w)^{n+1}}{z-w} \end{align*}.$$

Now we have

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

This is because the RHS is

$$\begin{align*} & \sum_{q=0}^n {n+1\choose q+1} w^q \sum_{p=0}^q z^p/w^p = \sum_{q=0}^n {n+1\choose q+1} w^q \frac{z^{q+1}/w^{q+1}-1}{z/w-1} \\ & = \sum_{q=0}^n {n+1\choose q+1} w^q \frac{z^{q+1}/w^{q}-w}{z-w} = \sum_{q=0}^n {n+1\choose q+1} \frac{z^{q+1}-w^{q+1}}{z-w} \\ & = \frac{1}{z-w} \left[ \sum_{q=0}^n {n+1\choose q+1} z^{q+1} - \sum_{q=0}^n {n+1\choose q+1} w^{q+1} \right] \\ & = \frac{1}{z-w} \left[ \sum_{q=-1}^n {n+1\choose q+1} z^{q+1} - \sum_{q=-1}^n {n+1\choose q+1} w^{q+1} \right] \\ & = \frac{1}{z-w} \left[(1+z)^{n+1}-(1+w)^{n+1}\right]. \end{align*}$$

Returning to the main sum we now see that it is given by

$$[z^m] [w^{r-m}] \sum_{q=0}^n {n+1\choose q+1} \sum_{p=0}^q z^p w^{q-p} = [z^m] [w^{r-m}] \sum_{p=0}^n \frac{z^p}{w^p} \sum_{q=p}^n {n+1\choose q+1} w^q.$$

With $m\le n$ we obtain

$$[w^{r-m}] \frac{1}{w^m} \sum_{q=m}^n {n+1\choose q+1} w^q = [w^r] \sum_{q=m}^n {n+1\choose q+1} w^q.$$

With $m\le r\le n$ this becomes at last

$$\bbox[5px,border:2px solid #00A000]{ {n+1\choose r+1}.}$$

The concluding step also follows by inspection seeing that $p=m$ and $q=r$ are the only combination $z^p w^{q-p}$ that can possibly contribute to $[z^m] [w^{r-m}].$

Answer 2

If we look at the sum, at first glance it seems that we can say, Choose $m$ of the first $k$ items, and $r-m$ of the remaining $n-k$ items, so in all we choose $r$ of $n$ items." There's some double counting going on though. When there are a string of unchosen items, which $k$ should the selection count against.

Having seen the problem, we fix it easily. Let item $k+1$ be the $m+1$st item chosen. Then choose $m$ of the items before it, and and $r-m$ of the items after it. This cover all ways to choose $r+1$ items out of $n+1$ and only those ways.

Answer 3

Fix $m$ and $r$, and use a generating function with respect to $n$: \begin{align} \sum_{n \ge 0} \sum_{k=m}^{n-r+m} \binom{k}{m} \binom{n-k}{r-m} z^n &= \sum_{k \ge m} \binom{k}{m} z^k \sum_{n\ge k+r-m} \binom{n-k}{r-m} z^{n-k} \\ &= \sum_{k \ge m} \binom{k}{m} z^k \frac{z^{r-m}}{(1-z)^{r-m+1}} \\ &= \frac{z^{r-m}}{(1-z)^{r-m+1}} \sum_{k \ge m} \binom{k}{m} z^k \\ &= \frac{z^{r-m}}{(1-z)^{r-m+1}} \cdot \frac{z^m}{(1-z)^{m+1}} \\ &= \frac{z^r}{(1-z)^{r+2}} \\ &= \frac{1}{z}\cdot\frac{z^{r+1}}{(1-z)^{r+2}} \\ &= \frac{1}{z} \sum_{n \ge r} \binom{n+1}{r+1} z^{n+1} \\ &= \sum_{n \ge r} \binom{n+1}{r+1} z^n \\ &= \sum_{n \ge 0} \binom{n+1}{r+1} z^n \end{align} Note that this "snake oil" approach derives the RHS of the desired identity without knowing it ahead of time.

Answer 4

Here is a plain algebraic derivation.

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n\binom{k}{m}\binom{n-k}{r-m}}&=\sum_{k=m}^{n-r+m}\binom{k}{m}\binom{n-k}{r-m}\tag{1}\\ &=\sum_{k=0}^{n-r}\binom{m+k}{k}\binom{n-m-k}{n-r-k}\tag{2}\\ &=\sum_{k=0}^{n-r}\binom{-m-1}{k}\binom{m-r-1}{n-r-k}(-1)^{n-r}\tag{3}\\ &=\binom{-r-2}{n-r}(-1)^{n-r}\tag{4}\\ &\,\,\color{blue}{=\binom{n+1}{r+1}}\tag{5} \end{align*} and the claim follows.

Comment:

• In (1) we set lower and upper index skipping terms which do not contribute to the sum.

• In (2) we shift the index to start with $k=0$ and use $\binom{p}{q}=\binom{p}{p-q}$.

• In (3) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ twice.

• In (4) we apply Chu Vandermonde's identity.

• In (5) we use the binomial identities from (2) and (3) again.

Note the nice nearly reciprocal relationship with the more familiar identity \begin{align*} \sum_{k=0}^n\binom{m}{k}\binom{r-m}{n-k}=\binom{r}{n} \end{align*}