## A proof in Set theory about the number of different subset in a Set

hi guys, I am a physics major, recently doing a few self-reading on analysis, however, I got stuck at some excises of proofs.

1. The problem statement, all variables and given/known data
If a set A contains n elements, prove that the number of different subsets of A is equal to $2^n$.

3. 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.

$$E(0)=1$$
$$E(1)=n$$
$$E(2)=\frac{n^2}{2}-\frac{n}{2}$$ (this is obtained from a bit of analysis. Possibly be fault however.)
$$E(3)=\frac{5n^3}{6} -\frac{n^2}{2}-\frac{n}{3}$$ (so is it.)
.
.
.
$$E(n)=1$$

However, I was almost driven crazy... I could't make the generl equation from it (which is hopefully $2^n$)

Any other approaches? Or any mistakes I made during my approach?

 PhysOrg.com science news on PhysOrg.com >> King Richard III found in 'untidy lozenge-shaped grave'>> Google Drive sports new view and scan enhancements>> Researcher admits mistakes in stem cell study

Mentor
 Quote by Shing hi guys, I am a physics major, recently doing a few self-reading on analysis, however, I got stuck at some excises of proofs. 1. The problem statement, all variables and given/known data If a set A contains n elements, prove that the number of different subsets of A is equal to $2^n$. 3. 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. $$E(0)=1$$ $$E(1)=n$$ $$E(2)=\frac{n^2}{2}-\frac{n}{2}$$ (this is obtained from a bit of analysis. Possibly be fault however.) $$E(3)=\frac{5n^3}{6} -\frac{n^2}{2}-\frac{n}{3}$$ (so is it.)
The formula above is incorrect. It should be (1/6)(n3 - 3n2 + 6n)
 Quote by Shing . . . $$E(n)=1$$ However, I was almost driven crazy... I could't make the generl equation from it (which is hopefully $2^n$) Any other approaches? Or any mistakes I made during my approach? Thanks for reading!
In general, and using your notation, E(m) = the number of combinations of n things taken m at a time, or nCm, which is defined to be n!/(m! (n - m)!).

For example, if n = 3, there are:
1 set with nothing in it -- {}
3 sets with 1 element -- {1}, {2}, {3}
3 sets with 2 elements -- {1, 2}, {1, 3}, {2, 3}
1 set with 3 elements -- {1, 2, 3}

All together there are 1 + 3 + 3 + 1 subsets, or 8 subsets, or 23 subsets.

By the same reasoning, it's easy to show that for a set with 4 elements, there are 24 subsets. You can use mathematical induction to show what you're trying to show; namely that for a set of n elements, there are 2n subsets.
 Thanks for answering! However, I would love to know how to prove nCm suitable here?

Recognitions:
Gold Member
 Probably my knowledge in Math induction is not enough. I have attempted to prove it via M.I. however, I was having some hard time my approach: 1.) obviously it is true for n=1,0 2.) I assume that it is true for $2^k$, where k belongs to natural set. 3.) but how do I know/prove it is also true for $2^{k+1}$? since I can't write such a function at all!
 Recognitions: Gold Member Science Advisor Staff Emeritus Suppose A contains k+ 1 elements, with k> 0. Let $a_0$ be one of the elements of A. Every subset of A either contains $a_0$ or it does not. If it does not, it is a subset of $A-\{x_0\}$ which has k elements so there are 2^k of them. If it does not, it is the same as a subset of $A- \{x_0\}$ union $x_0$ so there are $2^k$ of them. Together there are $2^k+ 2^k= 2(2^k)= 2^{k+1}$ subsets of A.