How many different ways to select a subset 
We want to select three subsets A, B, and C of {1, 2, . . . , n} so that A ⊆ C,
B ⊆ C, and A ∩ B $\ne$ ∅. In how many different ways can you do this?
This is my attempt:
Let A= $A_1$, B= $A_2$ and C = $A_1 \cup  A_2$. The set = $A_1 \cup  A_2 \cup A_3$. Then $3^n$ ways?
 A: We want to ensure that $A \subset C$ and $B \subset C$ such that $A \cap B \neq \emptyset$. 
We'll suppose that $A \cap B = \emptyset$, which are the cases that we don't want to account... Having in hands that formula, we can just subtract from all possible cases of sets $A$ and $B$ without restriction.
So suppose that the condition is: $A \subset C$ and $B \subset C$ such that $A \cap B = \emptyset$.
First suppose that $|A| = 0 \implies A = \emptyset$. Therefore $B$ can be any subset of $C$. It'll follow that for $A = \emptyset$ you can choose $B$ in $2^n$ different ways.
Now suppose that $|A| = 1$. The way how you pick $B$ defines $A$, so you only need to think about defining $B$. For that, $B$ can have any element different than the element that you picked for $A$. It can be of cardinality $0,1,\cdots,n-1$. If it's of cardinality $0$ than $B = \emptyset$. If it's of cardinality $1$ then you have $n-1 \choose 1$ ways to define it. If it's of cardinality $2$ then you have $n-1 \choose 2$ ways to define it... Continuing it in the same manner it'll follow that for $|A| = 1$ you could pick $B$ in:
$$
{n-1 \choose 0} + {n-1 \choose 1} + {n-1 \choose 2} + \cdots + {n-1 \choose n-1}
$$ways.
But you can pick $A$ for $|A| = 1$ in $n \choose 1$ different ways, so it'll follow that if $|A| = 1$ you would have:
$$
{n \choose 1} \cdot \bigg( {n-1 \choose 0} + {n-1 \choose 1} + {n-1 \choose 2} + \cdots + {n-1 \choose n-1} \bigg)
$$
ways to pick $A$ and $B$ such that the condition holds.
Using the same argument for the cardinality of $A$ over $\{0,1,2,3,\cdots,n\}$, it follows that the final answer is:
$$
\sum_{0 \leq j \leq n}{n \choose j} \cdot \bigg(\sum_{0 \leq i \leq j} {n-j \choose i}\bigg)
$$
If you use the following identity:
$$
\sum_{0 \leq i \leq n} {n \choose i} = 2^n
$$
then you can simplify the result as:
$$
\sum_{0 \leq j \leq n}{n \choose j} \cdot 2^{n-j} 
$$
And that is the number for the cases where $A \cap B = \emptyset$. All cases are given by $R = \{(a,b) \mid a \subset C \text{ and } b \subset C\}$. It's clear to see that $|R| = 2^n \cdot 2^n = 2^{2n}$. So our final answer is going to be:
$$
2^{2n} - \sum_{0 \leq j \leq n}{n \choose j} \cdot 2^{n-j} 
$$

Quick sanity check.
Suppose that $n = 3$, therefore $C = \{1,2,3\}$. Let's list all the possible combinations of the sets $A$ and $B$ such that $A \cap B = \emptyset$ and see if the first formula gives us the same result. A solution is going to be written as $(A,B)$. 
\begin{align*}
S_1 &= \{(\emptyset,\emptyset),(\emptyset,\{1\}),(\emptyset,\{2\}),(\emptyset,\{3\}),(\emptyset,\{1,2\}),(\emptyset,\{1,3\}),(\emptyset,\{2,3\}),(\emptyset,\{1,2,3\})\}\\
S_2 &= \{(\{1\},\emptyset),(\{1\},\{2\}),(\{1\},\{3\}),(\{1\},\{2,3\})\}\\
S_3 &= \{(\{2\},\emptyset),(\{2\},\{1\}),(\{2\},\{3\}),(\{2\},\{1,3\})\}\\
S_3 &= \{(\{3\},\emptyset),(\{3\},\{1\}),(\{3\},\{2\}),(\{3\},\{1,2\})\}\\
S_5 &= \{(\{1,2\},\emptyset),(\{1,2\},\{3\})\}\\
S_6 &= \{(\{1,3\},\emptyset),(\{1,3\},\{2\})\}\\
S_7 &= \{(\{2,3\},\emptyset),(\{2,3\},\{1\})\}\\
S_8 &= \{(\{1,2,3\},\emptyset)\}\\
\end{align*}
The number of solutions is the sum of the cardinalities of all the sets above. So it'll follow that it is:
$$
8 + (4 + 4 + 4) + (2 + 2 + 2) + 1 = 27
$$
which is indeed every term in the sum of our first formula:
\begin{align*}
{3 \choose 0} 2^3 + {3 \choose 1} 2^2 + {3 \choose 2} 2^1 + {3 \choose 3} 2^0 &= 1\cdot 8 + 3 \cdot 4 + 3 \cdot 2 + 1 \cdot 1\\
&= 8 + (4 + 4 + 4) + (2 + 2 + 2) + 1\\
&= 27
\end{align*}
So, using our last formula, it follows that $2^{6} - 27 = 37$ is the required number for $A \subset C$, $B \subset C$ and $A \cap B \neq \emptyset$.
Hope it helped :)

Doyun Nam's answer
It's a combinatorial identity that
$$
{n \choose 0} + 2{n \choose 1} + \cdots + 2^n{n \choose n} = 3^n
$$
So simplyfing even more my answer (last formula), we'll get:
$$
2^{2n} - \sum_{0 \leq j \leq n}{n \choose j} \cdot 2^{n-j} = 4^n - 3^n
$$
which is Doyun Nam corrected answer as pointed out by Ross Millikan in the comments.
A: Let $U = \{1, \ldots, n\}$. 
Then every elements should belong to one and only one of 
$A \cap B$, $A - B$, $B-A$, $C - (A\cup B)$, and $U-C$. 
And we should subtract the cases when $A \cap B = 0$ from the whole cases. 
Hence, there are $5^n - 4^n$ ways. 
