# Homework Help: Prove of number of subsets of a set

1. Jul 3, 2015

### rajeshmarndi

1. The problem statement, all variables and given/known data
A= {a1,.....am}, B= {b1,.....an}. If f: A→B is a function, then f(a1) can take any one of the n values b1,.....bn. Similarly f(a2). Then there are nm such function. I understand this part.

So in my book, using this principle,
nC0 + nC1 + ..... + nCn = 2n is proved.

It has taken a set A= {a1,.....an}. For each subset B of A, there is a function fB : A→ {0,1} given by fB(a1) = 1 if a1 ∈ B and fB(a1) = 0 otherwise. Conversely, for every f: A→ {0,1}, B = {a1 : fB(a1) =1 } ⊂ A anf f = fB. Thus there is a one-to-one correspondense between the subsets of A and the functions f: A→ {0,1}. From the above formula, hence we have
nC0 + nC1 + ..... + nCn = 2n

2. Relevant equations

3. The attempt at a solution The prove given is so short for me to understand anything.

2. Jul 3, 2015

### SammyS

Staff Emeritus
It may help to take the principle you are applying and restate it using other variables.

Let D= {d1, ... , dm}, R= {r1, ... , rn}. If f: D→R is a function, then f(d1) can take any one of the n values r1, ... , rn. Similarly for f(d2). Then there are nm such functions.​

Now apply this to the subset situation.

3. Jul 3, 2015

### rajeshmarndi

Sorry, that is the problem, I am unable to link the subset to the above mentioned situation.

4. Jul 3, 2015

### vela

Staff Emeritus
What's stopping you? What part don't you understand? Simply saying "I don't get it" isn't very helpful.