Cardinality of ordered pairs of subsets of {1, ..., n} computed in 2 different ways

Question

It is an assignment question, thus I am simply looking for a hint to unblock myself.

Let $S$ be a collection of all ordered pairs of subsets of $\{1, ..., n\}$, not necessarily disjoint. That is, $$ S = \{(A,B) : A \subseteq \{1, ..., n\}, b \subseteq \{1, ..., n\} $$ Show by computing the size of $S$ in the different ways that $$ 4^n = \sum_{k=0}^{n}{3^k{{n}\choose{k}}} $$

So far the left side is obvious that it is simply picking a $A$ then picking a $B$ in $\{1,...,n\}$. $$ |S| = 2^n \times 2^n = 4^n $$ The right side however is what has me stuck. Looking at the $3^k$, I can tell that it's the number of ways to pick $(A,B)$ disjoint subsets of $\{1,...,k\}$, $n\choose{k}$ is the number of ways to pick a third set. I've wrote ways to combine the third set into $(A,B)$ but I can't seem to find something intuitive that works for all $A, B$

Answer 1

Big hint: Let $S_k = \{(A,B) \in S : |A \cup B| = k\}$. Show that $|S_k| = 3^k \binom{n}{k}$.

$A\cup B$ is the disjoint union of $A \setminus B$, $B \setminus A$, and $A \cap B$. First choose $k$ numbers to belong to $A \cup B$ ($\binom{n}{k}$ ways to do this), and then distribute these $k$ numbers among the three sets ($3^k$ ways to do this).