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.