# Thread:

1. ## 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.

2. 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,
$\{ 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 8, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9564427137374878, "perplexity_flag": "middle"}