Clarification on Subsets of Natural Numbers and Bayes' Theorem I was trying to tackle this question and came across the following proposed solution. I am slightly confused about the proposed solution of part (a) of the question. The second part seems to be an extension of part (a). A verbal explanation describing how the first two steps were derived would suffice. 


By the definition of the conditional probability,
$$
\sum_{k=0}^n P(A \subset B | N_B = k) P(N_B = k) = \sum_{k=0}^n P(\overbrace{\{A \subset B\} \cap \{N_B = k\}}^{\text{disjoint sets}}) = P(\{A \subset B\} \cap \bigcup_{k=1}^n \{N_B = k\}) = P(A \subset B).
$$
Furthermore,
$$
P(N_B = k) = \frac{1}{2^n} \binom{n}{k} = \frac{1}{2^n} \frac{n (n-1) \cdots (n-k+1)}{k!},
$$
since you have $n (n-1) \cdots (n-k+1)$ possibilities to pick $k$ different items out of $n$ (where $B$ is the set of your 'items', which are the numbers $\{1, \ldots, n\}$) and $k!$ possible orders to pick them, and
$$
2^n = \sum_{j=0}^n \binom{n}{j}
$$
is the total number of subsets of $\{1, \ldots, n\}$. Similarly, $2^k$ is also the total number of subsets of a set of $k$ elements. Hence, once a fixed $C$ with $|C| = k$ is selected,
$$
P(A \subset C)= \frac{2^k}{2^n}.
$$
Thus,
$$
P(A \subset B | N_B = k) = \frac{\sum_{C \subset \{1, \ldots, n\} \atop |C| = k} \frac{2^k}{2^n}}{P(N_B = k)} = \frac{2^k}{2^n}.
$$
