# 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$

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

• Consider coefficient of $x^{n}$ in $[x^k(1-x)^{k+1}][x^k(1-x)^{k+1}]$. Jan 1, 2018 at 11:22

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

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:

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.