Counting pairs of subsets 
Let A be a finite set. Show that there are $3^n - 2^n$ tuples (X,Y)
  where $X \subset Y \subseteq A$ and $n = \#A$.

I tried to count the possibilities to build such tuples. There are $\sum_{k=1}^n \binom{n}{k}$ ways to build such a Y. Because of the condition $X \subset Y$ the corresponding $X$ may only contain less elements than $Y$. This leads me to $$\sum_{k=1}^n \binom{n}{k} \cdot \sum_{i=0}^{k-1} \binom{k}{i}$$ Even though this formula seems to be correct, I still don't bring it together with $3^n - 2^n$. Can you please help me to go on with this proof? 
 A: Hint:


*

*To count tuples $(X,Y)$ with $X \subseteq Y \subseteq A$, observe that each element $a \in A$ has three options: 


*

*$a \in X \land a \in Y$, 

*$a \notin X \land a \in Y$,

*$a \notin X, a \notin Y$.


Observe that $a \in X \land a \notin Y$ is not an option because of $X \subseteq Y$.
Therefore, there are $3^n$ such pairs of sets.

*To count tuples $(X,Y)$ with $X = Y \subseteq A$, each element has two options $a \in X = Y$ and $a \notin X = Y$, hence, $2^n$ such tuples.

*The smaller of the two above sets is contained in the other and
$$\Big\{(X,Y) \ \Big|\ X \subsetneq Y \subseteq A \Big\} = \Big\{(X,Y) \ \Big|\ X \subseteq Y \subseteq A \Big\} \setminus \Big\{(X,Y) \ \Big|\ X = Y \subseteq A \Big\}.$$


I hope this helps $\ddot\smile$
A: For your sum, note that:
$$
\sum_{0 \le r \le s} \binom{s}{r} = 2^s
$$
so that:
\begin{align}
\sum_{1 \le k \le n} \binom{n}{k} \sum_{0 \le i \le k - 1} \binom{k}{i}
  &= \sum_{1 \le k \le n} \binom{n}{k} (2^k - 1) \\
  &= \sum_{1 \le k \le n} \binom{n}{k} 2^k - \sum_{1 \le k \le n} \binom{n}{k} \\
  &= ((2 + 1)^n - 1) - (2^n - 1) \\
  &= 3^n - 2^n
\end{align}
