Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted


  • 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$

share|cite|improve this answer
great, thank you! – muffel Apr 19 '14 at 15:13

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}

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.