I am trying to get a combinatorial proof for this summation identity, for $0\leq k\leq \frac{n}{2}$ $$\sum_{m=k}^{n-k}\binom{m}{k}\binom{n-m}{k}=\binom{n+1}{2k+1}$$

The way I interpreted is that, for the right hand side $\binom{n+1}{2k+1}$ is the number of ways to choose $2k+1$ from total of $n+1$, then for left hand side, condition on dividing $n+1$ into two groups of size $m+1$ and $(n+1)-(m+1)=n-m$, then if choose $k$ the group of $n-m$ then it gives $\binom{n-m}{k}$, so there are $2k+1-k=k+1$ to choose from the group of size $m+1$, this is $\binom{m+1}{k+1}$, therefore I got the left hand side as $\sum_{m=k}^{n-k}\binom{m+1}{k+1}\binom{n-m}{k}\neq\sum_{m=k}^{n-k}\binom{m}{k}\binom{n-m}{k}$. what did I do wrong here? please help.


Suppose that you pick a set $A$ of $2k+1$ members of the set $[n+1]=\{1,\dots,n+1\}$. Let $A=\{a_0,\dots,a_{2k}\}$, where $a_0<a_1<\ldots<a_{2k}$. Then $k$ members of $A$ are less than $a_k$, and $k$ are greater. Let $A_0=\{a_0,\dots,a_{k-1}\}$ and $A_1=\{a_{k+1},\dots,a_{2k}\}$. Clearly $A_0\subseteq[a_k-1]$, so there are $\binom{a_k-1}k$ possibilities for $A_0$. Similarly, $A_1\subseteq[n+1]\setminus[a_k]$, so there are $\binom{n+1-a_k}k$ possibilities for $A_1$. Thus, for a fixed value $\ell$ of $a_k$ there are


possible $(2k+1)$-subsets $A$ of $[n+1]$. The minimum possible value of $\ell$ is $k+1$, since there must be at least $k$ smaller numbers in $[n+1]$, and the largest possible value is $n+1-k$. Let $m=\ell-1$; then $m$ ranges from $k$ through $n-k$, the expression $(1)$ becomes


and it’s now clear that summing $(2)$ from $m=k$ to $m=n-k$ is counting the $(2k+1)$-subsets of $[n+1]$ according to their middle elements.

In your approach you are in effect looking only at $A_0$ and $A_1$, but they don’t tell you where the cutoff between them is $-$ the $a_k$ in my construction.

  • $\begingroup$ @user62453: You’re welcome! $\endgroup$ – Brian M. Scott Mar 19 '13 at 17:38
  • $\begingroup$ You can avoid the switch from $\ell$ to $m=\ell+1$ by taking your initial $n+1$-set to be $\{0,1,\ldots,n\}$ rather than $\{1,2,\ldots,n+1\}$ (as I did in the answer I linked to). $\endgroup$ – Marc van Leeuwen Mar 22 '13 at 11:00

The way you are trying to set of things, there is no way to recover the value of $m$ from the subset chosen in the right hand side, so several choices of $m$ may lead to the same subset, and you're overcounting.

However if you take $m$ to be equal to the middle element of the selected subset taken in increasing order (that is the $k+1$-st smallest one), then you solve two difficulties: you can recover $m$ from the choice, and there remain onle $k$ elements to choose on either side of that value $m$. See this answer for handling a somewhat more general identity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.