Question: Given the set $X= \{(A,B):A,B \subset \{1,...n\}, A\subsetneq B\}$, find the cardinality of $X$. How can I do this?

Answer: 
For an alternative approach, which yields a combinatorial proof of the identity $$\sum\_m \binom{n}{m}(2^m-1)=3^n-2^n,$$ count the pairs $(A,B)$ as follows. For each $k\in\{1,\dots,n\}$, there are three disjoint possibilities:

1. $k\in A$ and $k\in B$
2. $k\notin A$ and $k\in B$
3. $k\notin A$ and $k\notin B$

This yields $3^n$ pairs $(A,B)$ with $A \subseteq B$, but $2^n$ of these have $A=B$, so subtract to obtain $3^n-2^n$.

---

Yet a third expression is obtained by choosing $A$ of size $k$ and then a nonempty subset for $B\setminus A$:
$$\sum\_{k=0}^{n-1} \binom{n}{k}(2^{n-k}-1)$$
Since you are counting ordered pairs (of sets), you can just do casework based on one of them, say $B.$ Start out with a simple case, say $B = \emptyset.$ Then there are no possibilities for $A,$ since the only subset of $B$ is the empty set and $A$ cannot equal $B.$ In the other extreme, if $B = \{1, ..., n\},$ then there are $2^n - 1$ choices for $A,$ since any subset of $\{1, ..., n\}$ will work except for the entire set. For a general choice of $B,$ there will be $2^m - 1$ choices for $A,$ where $m$ is the cardinality of $B.$

Summing over all the possibilities for $B,$ we find the result; using $\#(\cdot)$ to denote cardinality,

$$\#(X) = \sum\_{m = 0}^n \binom{n}{m} (2^m - 1),$$

where the binomial term describes the number of ways to choose $B$ with size $m$ in the first place.

Edit: You can show that the sum equals $\boxed{3^n - 2^n}.$