How many pairs $(A_1, A_2)$ of subsets of $\{1,2,\ldots,n\}$ are there such that $A_1 \cap A_2 = \emptyset$?
I am to give a solution involving binomial coefficients.
The hint I was given is to choose $A_1$ and then choose $A_2$ as a subset of its complement. Then determine the sum of products of binomial coefficients.
I do not know where to begin, so any guidance is appreciated.
Take any $k \in \{ 0,...,n \}$ and say that set $A_1$ will have $k$ elements chosen from $\{1,...,n\}$. Then there are $n-k$ elements left, and set $A_2$ can be any subset of set of those remaining elements. That is, for a fixed $k$, we have ${n \choose k}$ ways of choosing $A_1$, then for every $A_1$ (cause this is only matter of $|A_1|$) we have $2^{n-k}$ ways to choose $A_2$. Now we have to sum over all values $k$, which gives us: $\sum_{k=0}^n {n \choose k} 2^{n-k}$.
However, we can count it in different way. Note, that since we want $A_1 \cap A_2 = \emptyset$, that means we can form a set $A_3$ (for every choice of $A_1,A_2$) containing only those elements, which are in set $\{1,...,n\}$ and aren't in $A_1$ nor $A_2$. So we can say, we're just considering triples $(A_1,A_2,A_3)$, where $A_i \cap A_j = \emptyset$, for every $i,j \in \{1,2,3\} $, $ i \neq j$. And $A_1 \cup A_2 \cup A_3 = \{1,...,n\}$. How to do this? Just take elements in $\{1,...,n\}$ one by one, and ask yourself, whether u want to put it in $A_1,A_2$ or $A_3$. How many ways it gives? Well, there are $n$ elements, and $3$ choices for every, so $3^n$.
We ended up with $\sum_{k=0}^n {n \choose k} 2^{n-k} = 3^n$