Is there an algebraic proof for $\sum_{m=k}^{n-k} \binom{m}{k}\binom{n-m}{k} = \binom{n+1}{2k+1}, n\ge2k\ge0$

Question

$\sum_{m=k}^{n-k} \binom{m}{k}\binom{n-m}{k} = \binom{n+1}{2k+1}, n\ge2k\ge0$

An combinatorial proof of the identity above states as follow:

(1)Number of ways of picking (2k+1) numbers from 1 to (n+1) should be $\binom{n+1}{2k+1}$

(2)We pick (2k+1) numbers from 1 to (n+1) with median value (m+1). Then, k numbers must be selected from 1~m, and the other k numbers must be chosen from (m+2)~(n+1). Thus there are $\binom{m}{k}\binom{n-m}{k}$ ways for picking (2k+1) numbers with median value (m+1). Since $n-k\ge m\ge k$, there are total $\sum_{m=k}^{n-k} \binom{m}{k}\binom{n-m}{k}$ ways.

Since (1)=(2), the statement is true. But is it possible to sketch an algebraic proof that doesn't require building combinatorial models?

Answer 1

Here is an algebraic proof based upon generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{m=k}^{n-k}}&\color{blue}{\binom{m}{k}\binom{n-m}{k}}\\ &=\sum_{m=0}^{n-2k}\binom{m+k}{m}\binom{n-m-k}{k}\tag{1}\\ &=\sum_{m=0}^{n-2k}\binom{-k-1}{m}(-1)^m\binom{n-m-k}{k}\tag{2}\\ &=\sum_{m=0}^\infty[z^m](1-z)^{-k-1}[u^k](1+u)^{n-m-k}\tag{3}\\ &=[u^k](1+u)^{n-k}\sum_{m=0}^\infty\left(\frac{1}{1+u}\right)^{m}[z^m](1-z)^{-k-1}\tag{4}\\ &=[u^k](1+u)^{n-k}\left(1-\frac{1}{1+u}\right)^{-k-1}\tag{5}\\ &=[u^k](1+u)^{n-k}u^{-k-1}(1+u)^{k+1}\tag{6}\\ &=[u^{2k+1}](1+u)^{n+1}\tag{7}\\ &\color{blue}{=\binom{n+1}{2k+1}}\tag{8} \end{align*} and the claim follows.

Comment:

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

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

• In (3) we apply the coefficient of operator twice and we set the upper bound of the series to $\infty$ without changing anything since we are adding zeros only.

• In (4) we use the linearity of the coefficient of operator and we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (5) we apply the substitution rule of the coefficient of operator with $z=\frac{1}{1+u}$
  \begin{align*} A(u)=\sum_{m=0}^\infty a_m u^m=\sum_{m=0}^\infty u^m [z^m]A(z) \end{align*}

• In (6) we do some simplifications.

• In (7) we do some more simplifications and apply the same rule as we did in (4).

• In (8) we select the coefficient of $u^{2k+1}$.

Answer 2

More generally:

Theorem 1. For every nonnegative integers $x$, $y$ and $n$, we have \begin{equation} \dbinom{n+1}{x+y+1}=\sum_{m=0}^{n}\dbinom{m}{x}\dbinom{n-m}{y}. \end{equation}

This equality rewrites as \begin{equation} \dbinom{n+1}{x+y+1} = \sum_{m=x}^{n-y} \dbinom{m}{x}\dbinom{n-m}{y} , \end{equation} because all addends $\dbinom{m}{x}\dbinom{n-m}{y}$ are zero except for those where $x \leq m \leq n-y$.

Your identity is the particular case of the latter equality for $x = k$ and $y = k$.

Your nice bijective proof of the original identity can easily be generalized to a proof of Theorem 1; just count all ways of picking an $\left(x+y+1\right)$-element subset of $\left\{1,2,\ldots,n+1\right\}$ according to the value of the $\left(x+1\right)$-th-lowest element of the subset. Indeed, for any given $m \in \left\{0,1,\ldots,n\right\}$, picking an $\left(x+y+1\right)$-element subset $S$ of $\left\{1,2,\ldots,n+1\right\}$ whose $\left(x+1\right)$-th-lowest element is $m+1$ is tantamount to picking an $x$-element subset of $\left\{1,2,\ldots,m\right\}$ (which will contain the $x$ elements of $S$ lower than $m+1$) and picking a $y$-element subset of $\left\{m+2,m+3,\ldots,n+1\right\}$ (which will contain the $y$ elements of $S$ higher than $m+1$). This gives $\dbinom{m}{x}\dbinom{n-m}{y}$ for the number of choices.

As for other proofs:

• An elementary proof is given in Proposition 3.32 (f) in Darij Grinberg, Notes on the combinatorial fundamentals of algebra, Version of 10 January 2019. The proposition is obtained from Vandermonde convolution by several applications of upper negation.

• Theorem 1 is also equivalent to the identity proven in Proof of $\sum_{m=0}^{n}\binom{m}{j}\binom{n-m}{k-j}=\binom{n+1}{k+1}$ (Another form of the Chu–Vandermonde identity) (just set $j = x$ and $k = x+y$); the proof uses generating functions.

Answer 3

A direct calculation:

$$\sum_{m=k}^{n-k}\binom{m}{k}\binom{n-m}{k}=\sum_{m=k}^{n-k}\binom{m}{m-k}\binom{n-m}{n-m-k}$$$$=\sum_{m=k}^{n-k}\left(-1\right)^{m-k}\binom{-k-1}{m-k}\left(-1\right)^{n-m-k}\binom{-k-1}{n-m-k}$$$$=\left(-1\right)^{n}\sum_{m=k}^{n-k}\binom{-k-1}{m-k}\binom{-k-1}{n-m-k}=\left(-1\right)^{n}\binom{-2k-2}{n-2k}$$$$=\binom{n+1}{n-2k}=\binom{n+1}{2k+1}$$

Hence we showed that: $$\bbox[5px,border:2px solid #00A000]{\sum_{m=k}^{n-k}\binom{m}{k}\binom{n-m}{k}=\binom{n+1}{2k+1}}$$

As desired.