Number of pairs $(A, B)$ such that $A \subseteq B$ and $B \subseteq \{1, 2, \ldots, n\}$ I need to determine the number of pairs $(A,B)$ of sets such that $A \subseteq B$ and $B \subseteq \{1,2,\ldots,n\}$
My solution:
How $A \subseteq B$ and $B \subseteq \{1,2,\ldots,n\}$, we have:
$$A :=  B := \sum_{i = 0}^{n} \left(\begin{array}{c} n \\ i \end{array} \right)$$
in this way, we have that the number of pairs $(A,B)$ of sets are:
$$\sum_{i=1}^{n} \left( \begin{array}{c} n \\ i \end{array}\right) + \frac{\sum_{i=1}^{n} \left( \begin{array}{c} n \\ i \end{array}\right)}{2} \cdot \left( \begin{array}{c} n \\ 0 \end{array}\right) + \left( \begin{array}{c} n \\ 0 \end{array}\right) \\ 2^n + 2^{n-1} + 1 $$
Here is a little example.
Suppose $n = 2$ 
Then $A \subseteq B$ and $B \subseteq \{1,2\}$. With this, we have:
$$(A, B) = (\emptyset,\emptyset), (\emptyset,{1}), (\emptyset,{2}), (\emptyset, {1,2}), ({1}, {1}), ({1}, {1,2}), ({1,2}, {1,2})$$
 A: We use $[n]$ to denote the set of natural numbers $\{1,2,\ldots,n\}$.

We obtain
\begin{align*}
\color{blue}{\sum_{{(A,B)}\atop{A\subseteq B\subseteq[n]}}1}
&=\sum_{B\subseteq [n]}\sum_{A\subseteq B}1\\
&=\sum_{j=0}^n\sum_{{B\subseteq [n]}\atop{|B|=j}}\sum_{k=0}^j\sum_{{A\subseteq B}\atop{|A|=k}}1\tag{1}\\
&=\sum_{j=0}^n\binom{n}{j}\sum_{k=0}^j\binom{j}{k}\tag{2}\\
&=\sum_{j=0}^n\binom{n}{j}2^j\tag{3}\\
&\,\,\color{blue}{=3^n}\tag{4}
\end{align*}

Comment:

*

*In (1) we rearrange the sum according to terms with increasing size of subsets $A$ and $B$.


*In (2) we use the fact that the number of subsets of size $q$ of a finite set $X$ is $\binom{|X|}{q}$.


*In (3) and (4) we apply the binomial theorem.

Example: $n=2$
We have the following $3^2=9$ pairs $(A,B)$ when considering $[2]=\{1,2\}$:
\begin{align*}
&(\emptyset,\emptyset),\\
&(\emptyset,\{1\}),\,(\{1\},\{1\}),\\
&(\emptyset,\{2\}),\,(\{2\},\{2\}),\\
&(\emptyset,\{1,2\})\,(\{1\},\{1,2\}),\,(\{2\},\{1,2\}),\,(\{1,2\},\{1,2\})
\end{align*}

A: To each of the elements of $\{1,2,\ldots,n\}=[n]$, we assign a $a,b$ or $c$, independently. We have $3^n$ ways to do this.
For each assignment we make a pair $(A,B)$ as follows: if $i \to a$ we put $i$ in $A$ and also in $B$, if $i \to b$ we put $i$ in $B$ and if $i \to c$ we put it in neither $A$ nor $B$. Then $(A,B)$ is a good pair and to each such pair there is also a unique such assignment as above (based on the partition $A$,$B \setminus A$, $[n]\setminus (A \cup B)$, etc. So there are also $3^n$ such pairs.
A: First we count the possibilities for $B$.  So if $B$ has $k$ elements, $0 \leq k \leq n$, then there are ${n \choose k}$ possibilities. For each of these possibilities for $B$, there are
$$ \sum_{i=0}^{{n \choose k}} {{n \choose k} \choose i} $$
possibilities for $A$. So to conclude, if $B$ has $k$ elements, then there are
$$ {n \choose k} \cdot \sum_{i=0}^{{n \choose k}} {{n \choose k} \choose i} $$
possible pairs of sets $(A,B)$.
Since we can choose any $0 \leq k \leq n$, sum over all values of $k$:
$$ \sum_{k=0}^{n} \left( {n \choose k} \cdot \sum_{i=0}^{{n \choose k}} {{n \choose k} \choose i} \right)$$
