Results 1 to 2 of 2

Math Help - Summation identity proof

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    39

    Summation identity proof

    I am having trouble proving this identity:

    \sum_{k=0}^n n \choose k m - n \choose n - k = m \choose n

    It gives a hint that you should try to interpret each of the summands.

    I can't seem to use induction because there are factorials involved. And the summands don't have items that cancel out. It does seem related to a hypergeometric distribution however.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by cubs3205 View Post
    I am having trouble proving this identity:

    \sum_{k=0}^n{n \choose k}{m - n \choose n - k} = {m \choose n}

    It gives a hint that you should try to interpret each of the summands.
    Here's the idea for a combinatorial proof (it seems to be the one the hint suggests).
    m\choose n is the number of subsets of \{1,\ldots m\} with n elements.
    n\choose k is the number of subsets of \{1,\ldots n\} with k elements.
    m-n\choose n-k is the number of subsets of \{n+1,\ldots m\} with n-k elements.

    Do you get it? Any n-element subset of \{1,\ldots,m\} provides both a k-element subset of \{1,\ldots,n\} and an (n-k)-element subset of \{n+1,\ldots,m\}, where k\in\{1,\ldots,n\}. And vice-versa. And this is what the equality says.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof of summation
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 18th 2011, 08:30 PM
  2. Summation identity
    Posted in the Algebra Forum
    Replies: 6
    Last Post: July 17th 2011, 09:14 PM
  3. Cosine Summation Identity
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: May 17th 2011, 07:52 AM
  4. Summation proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 25th 2011, 11:08 PM
  5. summation identity proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 2nd 2007, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum