Results 1 to 2 of 2

Thread: Summation identity proof

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    39

    Summation identity proof

    I am having trouble proving this identity:

    $\displaystyle \sum_{k=0}^n$ $\displaystyle n \choose k$ $\displaystyle m - n \choose n - k$ = $\displaystyle 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:

    $\displaystyle \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).
    $\displaystyle m\choose n$ is the number of subsets of $\displaystyle \{1,\ldots m\}$ with $\displaystyle n$ elements.
    $\displaystyle n\choose k$ is the number of subsets of $\displaystyle \{1,\ldots n\}$ with $\displaystyle k$ elements.
    $\displaystyle m-n\choose n-k$ is the number of subsets of $\displaystyle \{n+1,\ldots m\}$ with $\displaystyle n-k$ elements.

    Do you get it? Any $\displaystyle n$-element subset of $\displaystyle \{1,\ldots,m\}$ provides both a $\displaystyle k$-element subset of $\displaystyle \{1,\ldots,n\}$ and an $\displaystyle (n-k)$-element subset of $\displaystyle \{n+1,\ldots,m\}$, where $\displaystyle 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: Sep 18th 2011, 08:30 PM
  2. Summation identity
    Posted in the Algebra Forum
    Replies: 6
    Last Post: Jul 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: Feb 25th 2011, 11:08 PM
  5. summation identity proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Mar 2nd 2007, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum