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

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

3 Answers 3


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.


  • 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:


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .