1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinations proof

  1. Mar 8, 2012 #1
    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. jcsd
  3. Mar 8, 2012 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. Mar 8, 2012 #3
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinations proof
  1. A proof (Replies: 2)

  2. A proof! (Replies: 0)

Loading...