Results 1 to 2 of 2

Math Help - Power sets

  1. #1
    Junior Member
    Joined
    Jul 2007
    Posts
    27

    Question Power sets

    I have a homework problem that I knew the answer but dont know how to do the proof. Can anyone help me?

    List all the subsets of the set X={a,b,c}. How many are there? Next, try with X={a,b,c,d). Now suppose that the set X has n elements: how many subsets does X have? Try to justify your answer.

    I do the first part as
    For X={a,b,c}
    {},
    {a},{b},{c},
    {a,b},{a,c},{b,c}
    {a,b,c}
    which is 1,3,3,1
    For X={a,b,c,d}, in the same pattern, which is 1,4,6,4,1.

    I think it is the Pascal triangle's pattern and the answer is 2^n, but I have no idea how to write the proof.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by r7iris View Post
    I have a homework problem that I knew the answer but dont know how to do the proof. Can anyone help me?

    List all the subsets of the set X={a,b,c}. How many are there? Next, try with X={a,b,c,d). Now suppose that the set X has n elements: how many subsets does X have? Try to justify your answer.

    I do the first part as
    For X={a,b,c}
    {},
    {a},{b},{c},
    {a,b},{a,c},{b,c}
    {a,b,c}
    which is 1,3,3,1
    For X={a,b,c,d}, in the same pattern, which is 1,4,6,4,1.

    I think it is the Pascal triangle's pattern and the answer is 2^n, but I have no idea how to write the proof.
    It is 2^n.

    Consider,
    \{ 1,2,...,n\}

    There is the one empty set, which is {n\choose 0}

    There are n singleton sets, which is {n\choose 1}

    There are n(n-1)/2 two elements sets which is {n\choose 2}.

    And so on ...

    Until we use all the elements, and the full set itself which is {n\choose n}.

    In total we have,
    {n\choose 0}+{n\choose 1}+...+{n\choose n}=2^n

    See if you can figure out the last line.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 05:26 PM
  2. Power Sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2009, 02:27 AM
  3. Crossing power sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2009, 06:24 PM
  4. Crossing power sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 29th 2009, 01:30 PM
  5. Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 22nd 2008, 08:43 AM

Search Tags


/mathhelpforum @mathhelpforum