# Homework Help: Combinations proof

1. Mar 8, 2012

### gsingh2011

1. The problem statement, all variables and given/known data
Prove that for any positive integer n, k,
$$\binom{n}{2k+1}=\sum_{i=1}^n{\binom{i-1}{k}\binom{n-i}{k}}$$

2. Relevant equations
$$\binom{n}{k}=\frac{n!}{(n-k)!k!}$$

3. The attempt at a solution
I'm looking for a starting point. I've been given a hint that says,
But I don't know how to do that, or what to do from there.

2. Mar 8, 2012

### Office_Shredder

Staff Emeritus
I think the hint is a bit poorly worded, but here's the idea:

On the left, in a set of size n we are picking 2k+1 elements. Consider the set to literally be the numbers 1 through n. Split your set into two parts - the numbers smaller than the median of the 2k+1 numbers you picked, and the numbers larger than it.

On the other hand, each term in the summand is counting the ways to: pick k elements from an i-1 sized set, and pick k elements from an n-i sized set. If we combine those two together, we are essentially picking 2k elements from a set of size n-1.

3. Mar 8, 2012

### gsingh2011

Thanks, but I'm still not sure what to do from here. I'm not sure how to deal with the sum, I guess.

EDIT: I guess I kind of get it now. For the summand, if we keep changing i then we're finding the number of ways to choose 2k elements from n-1 elements by choosing them from each sized set. So I guess my problem now is understanding why it's n-1 and 2k instead of n and 2k+1.

Last edited: Mar 8, 2012