Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer

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

$$\binom{\ell-1}k\binom{n+1-\ell}k\tag{1}$$

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

$$\binom{m}k\binom{n-m}k\;,\tag{2}$$

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.

share|improve this answer
    
Awesome, thank you!! –  user62453 Mar 19 '13 at 17:38
    
@user62453: You’re welcome! –  Brian M. Scott Mar 19 '13 at 17:38
    
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). –  Marc van Leeuwen Mar 22 '13 at 11:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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