Probability of Sets I need some help on this one:
We have sets $X$ and $Y$ chosen independently and uniformly at random from among all subsets of $\{1,2,\ldots,100\}$. Determine the probability that $X$ is a subset of $Y$.

how many pairs $(X,Y)$ satisfy $X\subseteq Y$? classify according to the size of $Y$.
So we get $\sum\limits_{k=0}^n\binom{n}{k}2^k$.
Since there are $2^n\times 2^n$ possible pairs $(X,Y)$ you want $$\frac{\sum\limits_{k=0}^n\binom{n}{k}2^k}{2^{2n}}$$
Now notice that $\sum\limits_{k=0}^n\binom{n}{k}2^k$ is equal to $3^n$ because it is the number of ways to color the integers from $1$ to $n$ with colors white grey and black. To see this we could say we are indexing on the number of elements that are grey or black (So first pick the subset of numbers that are grey or black) And once that subset has been selected choose the subsets of that subset that is going to be black. Hence uniquely determining the coloring.
