How do you show the number of subsets of a set is 2^n?

[Zeigy]

How do you show the number of subsets of a set is 2^n?

Can someone show this to me using sequences and not combinations?

[Hello Actuaria/ Stars]

I'm not sure what the question is exactly. Can you define your terms more specifically?

[Zeigy]

Okay. Well the question goes something like this:

You have a set, say U which has n elements, U = {u₁, u₂, ...,un}. I want to show that 2ⁿ is the number of subsets of U inclusive of U and the null set.

For each subset S of U define the sequence (s₁, s₂, ..., sn) such that si = 1 if xi ϵ S and 0 otherwise. Then count the number of sequences.

[NoMoreExams]

Okay. Well the question goes something like this:

You have a set, say U which has n elements, U = {u₁, u₂, ...,un}. I want to show that 2ⁿ is the number of subsets of U inclusive of U and the null set.

For each subset S of U define the sequence (s₁, s₂, ..., sn) such that si = 1 if xi ϵ S and 0 otherwise. Then count the number of sequences.

You should probably find a math board and ask intro to proofs or real analysis or whatever subject this is from there. Additionally have you tried google? This is like one of the first proofs that gets asked in those types of classes. If you weren't forced to do with sequences. you can do it with induction for example.

[DG11]

Consider a set of n elements. From this set we can form subsets from 0 of these elements (the null set), up to a set of all n elements. We can represent this situation bu summing nCr from 0 to n, as follows:

∑(r=0,n) nCr

Now note the Binomial Theorem.
∑(r=0,n) nCr * a^(n-r) * b^r
= (a + b)^n
= a^n + n*a^(n-1)*b + nC2*a^(n-2)*b^2 + ... + nCr*a^(n-r)*b^r + ... + nC(n-1)*a*b^(n-1) + b^n

Now if we let a = 1, and b = 1, the Binomial Theorem becomes:
∑(r=0,n) nCr * (1)^(n-r) * (1)^r
= ∑(r=0,n) nCr
= (1 + 1)^n
= 2^n

[Zeigy]

Thank you. I'm going to analyse this.

[Zeigy]

Hello I have a new question. It's from a text but because it's copyrighted I'm going to post a similar question.

A car company orders a shipment of 50 Toyota Prius'. 5 are found to have defective accelerator pedals. If 4 Prius' are chosen at random for a test drive. What is the probability that 2 are good and 2 are defective?

I was working on this problem all morning. I found the solution by using a tree diagram and calculating the probabilities of choosing 6 out of the sixteen outcomes of choosing 4 cars.

Is there an easier and faster way to work this question?

[BeanCounter]

I think this is a hypergeometric problem. [(5C2) * (45C2)] / (50C4) would work.

[Hello Actuaria/ Stars]

Yup, it's hypergeometric. Whenever you see a problem that involves sampling without replacement, and the sample size is small, you should check if the hypergeometric works.

The hypergeometric is really easy to use once the concept behind it sinks in (which might take a while). The concept behind it is this: You want 2 defective and 2 good. You first find the number of ways you can choose 2 defective pedals out of the 5 that are in the sample, then you multiply that by the number of ways you can get 2 good pedals out of the 45 in the sample. That gives you the total NUMBER of ways you can get a combintation 2 good and 2 defective pedals. However, we are looking for the probability, not the number, so we have to divide that by the overall number of ways to get 4 pedals.

If you'd like to understand the concept behind the hypergeometric better, you could try figuring out how they got all the poker probabilities here: http://en.wikipedia.org/wiki/Poker_probability. By the time you are done the hypergeometric will look easy.

[Zeigy]

Thank you BeanCounter, thank you Actuaria. I get it now. Onwards with the exercises.

[Zeigy]

Actuaria, this link is very useful. I was actually stuck on a poker question and the explanation for finding the probability for a two pair hand came in handy. Probability is so intuitive. I understand now why practice is so important to increase speed and the intuitive process.

[PJA]

Nvm someone already explained it this way.

[Zeigy]

I have a mystery. I'm doing this problem. I had no trouble finding E(X) and Var(X). However:

E[|X - μ|] = E[|X - ⅔|] = ∫(⅔ - x)(2x) dx + ∫(x - ⅔)(2x) dx

The lower and upper boundaries of the first integral is 0 and ⅔, the second is ⅔ and 1.

The pdf is f(x) = 2x for 0 < x < 1.

When I was working it out I thought my answer would be:

E[|X - μ|] = E[|X - ⅔|] = ∫(x - ⅔)(2x) dx

with integral lower and upper boundaries of 0 and 1.

Where did I go wrong? Why is this:

E[|X - μ|] = E[|X - ⅔|] = ∫(⅔ - x)(2x) dx + ∫(x - ⅔)(2x) dx

correct?

[NoMoreExams]

I have a mystery. I'm doing this problem. I had no trouble finding E(X) and Var(X). However:

E[|X - μ|] = E[|X - ⅔|] = ∫(⅔ - x)(2x) dx + ∫(x - ⅔)(2x) dx

The lower and upper boundaries of the first integral is 0 and ⅔, the second is ⅔ and 1.

The pdf is f(x) = 2x for 0 < x < 1.

When I was working it out I thought my answer would be:

E[|X - μ|] = E[|X - ⅔|] = ∫(x - ⅔)(2x) dx

with integral lower and upper boundaries of 0 and 1.

Where did I go wrong? Why is this:

E[|X - μ|] = E[|X - ⅔|] = ∫(⅔ - x)(2x) dx + ∫(x - ⅔)(2x) dx

correct?

Because x - 2/3 is > 0 for x > 2/3 and < 0 for x < 2/3

[Zeigy]

I'm still kind of confused with the (⅔ - x) of the first integral. Am I to understand that |X - ⅔| is (X - ⅔) and -(X - ⅔) or (⅔ - X) so that,

0 < X - ⅔ < 1
⅔ < X < 1⅔

since the boundaries for the function are between 0 and 1 then we dont use 1⅔ but 1 for the second integral so it has lower and upper boundaries between ⅔ and 1.

And for the first integral:

0 < ⅔ - X < 1
-⅔ < -X < ⅓
⅔ > X > -⅓
-⅓ < X < ⅔

because the lower boundary is 0 we exclude -⅓ and start the first integral from 0 to ⅔ ?