- #1
Shing
- 144
- 1
hi guys, I am a physics major, recently doing a few self-reading on analysis, however, I got stuck at some excises of proofs.
If a set A contains n elements, prove that the number of different subsets of A is equal to [itex]2^n[/itex].
First, I teared apart the problem, attempting to draw a general equation from looking at the numbers of different subset one by one.
E(m) regarded as the possible number of different subsets which contains m elements, whereas A has total n elements.
[tex]E(0)=1[/tex]
[tex]E(1)=n[/tex]
[tex]E(2)=\frac{n^2}{2}-\frac{n}{2}[/tex] (this is obtained from a bit of analysis. Possibly be fault however.)
[tex]E(3)=\frac{5n^3}{6} -\frac{n^2}{2}-\frac{n}{3}[/tex] (so is it.)
.
.
.
[tex]E(n)=1[/tex]
However, I was almost driven crazy... I could't make the generl equation from it (which is hopefully [itex]2^n[/itex])
Any other approaches? Or any mistakes I made during my approach?
Thanks for reading!
Homework Statement
If a set A contains n elements, prove that the number of different subsets of A is equal to [itex]2^n[/itex].
The Attempt at a Solution
First, I teared apart the problem, attempting to draw a general equation from looking at the numbers of different subset one by one.
E(m) regarded as the possible number of different subsets which contains m elements, whereas A has total n elements.
[tex]E(0)=1[/tex]
[tex]E(1)=n[/tex]
[tex]E(2)=\frac{n^2}{2}-\frac{n}{2}[/tex] (this is obtained from a bit of analysis. Possibly be fault however.)
[tex]E(3)=\frac{5n^3}{6} -\frac{n^2}{2}-\frac{n}{3}[/tex] (so is it.)
.
.
.
[tex]E(n)=1[/tex]
However, I was almost driven crazy... I could't make the generl equation from it (which is hopefully [itex]2^n[/itex])
Any other approaches? Or any mistakes I made during my approach?
Thanks for reading!