Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

up vote 2 down vote accepted

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$

share|improve this answer
    
great, thank you! –  muffel Apr 19 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|improve this answer

Your Answer

 
discard

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.