Results 1 to 5 of 5

Math Help - Prove the identity using a combinatorial proof

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    56

    Prove the identity using a combinatorial proof

    Prove the identity

    \displaystyle \sum_{k=0}^{n} k {n \choose k} = n 2^{n-1}
    Attached Thumbnails Attached Thumbnails Prove the identity using a combinatorial proof-785091c89b91773535544515523d773b.png  
    Last edited by mr fantastic; April 7th 2011 at 05:56 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    Uhm, what did you try to do?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    56
    I try to use a combinatorial proof that both side of the equation count the same thing.
    Because I don't know how to try the equation, so I insert the image of it here. (785091c89b91773535544515523d773b.png)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    Write here that attempt and i will help you.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2009
    Posts
    4
    I am also struggling with this same problem, and here is my attempted reasoning after many hours of thought:

    Suppose S = {1,2,...,n}; that is, |S|=n. I found it helpful to think about "committees" of people. So let |S| = n be the total number of people. So the LHS counts the total number of all possible committees with a certain unique number of each. Writing out the sum it's easier to see this way: There are C(n,1)=n ways to make a committee of one person, and we only desire 1 of these committees. There are C(n,2) ways to make another committee of two people, we wish to have 2 of these. There are C(n,3) ways to make a third committee of three people; we wish to have 3 of these. And so on and so forth up to our n committees of all n people. Note that the power set of S, P(S), has size |P(S)|=2^n. So we have 1 + ... + n = (n+1)n/2 committees size 1 through n, respectively. But we must divide by (n+1) since the committees are distinct. Thus, by the multiplication principle, we have (2^n)*(n/2) = n*2^(n-1).

    Again, this is my reasoning. I feel like there may be a flaw somewhere, and would appreciate any input to make my argument sound better (or even to know if it is valid).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial proof for an identity
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: April 23rd 2011, 04:12 PM
  2. Combinatorial proof of derangement identity
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 29th 2010, 02:40 PM
  3. interesting combinatorial identity proof
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: November 29th 2009, 04:34 PM
  4. [SOLVED] Prove the following combinatorial identity?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 13th 2009, 06:56 AM
  5. Combinatorial proof of a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 12th 2008, 02:42 PM

Search Tags


/mathhelpforum @mathhelpforum