Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was curious if anyone might be able to give me a hint as to how one might show the following identity combinatorially:

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

For the left hand side I reason that we are choosing, for example, one object out of $1$ type, then choose from $4$ other types for another object. Continuing on we take $1$ object from $2$ types and then select another object from the remaining $3$ types. The right hand side seems to be telling us something about picking an odd number of objects, which makes me think my initial attempt might have been off the mark and there is instead I should focus on parity. Perhaps I'm missing something simple?

share|cite|improve this question

marked as duplicate by Marc van Leeuwen, Amzoti, vonbrand, Micah, Emily Apr 22 '13 at 15:27

This question was marked as an exact duplicate of an existing question.

up vote 0 down vote accepted

HINT: Consider the task of choosing $2k+1$ numbers from the set $\{0,1,\dots,n\}$ of $n+1$ integers. Let the numbers chosen be $a_0,\dots,a_{2k}$, listed in increasing order. Set $m=a_k$, so that $k$ of the chosen elements precede $m$ and $k$ follow $m$.

share|cite|improve this answer
    
I definitely see where I went wrong now, thanks! – 114 Apr 3 '13 at 2:30
    
@Stopwatch: You’re welcome! – Brian M. Scott Apr 3 '13 at 2:31

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