Power sets

• Jul 22nd 2007, 07:03 PM
r7iris
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.
• Jul 22nd 2007, 07:21 PM
ThePerfectHacker
Quote:

Originally Posted by r7iris
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,
\$\displaystyle \{ 1,2,...,n\}\$

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

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

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

And so on ...

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

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

See if you can figure out the last line.