Prove Combinations Proof: Median Method

[gsingh2011]

Homework Statement

Prove that for any positive integer n, k,
$$\binom{n}{2k+1}=\sum_{i=1}^n{\binom{i-1}{k}\binom{n-i}{k}}$$

Homework Equations

$$\binom{n}{k}=\frac{n!}{(n-k)!k!}$$

The Attempt at a Solution

I'm looking for a starting point. I've been given a hint that says,

Classify (2k + 1)-sets of size n by what the median is, where (2k + 1)-sets of size n means the subsets of size n containing (2k + 1) elements.

But I don't know how to do that, or what to do from there.

 

[Office_Shredder]

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.

 

[gsingh2011]

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.

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.