# Prove $3^n = \sum_{0 \leq i \leq j \leq n}$ $n \choose i$ $i \choose j$

How to prove $3^n = \sum_{0 \leq j \leq i \leq n}$ $n \choose i$ $i \choose j$ using $3^n = \sum_{0 \leq i \leq n} 2^i$ $n \choose i$

-
$2 = 1+1$. :-) Also, shouldn't it be $j \leq i$? –  WimC Nov 19 '12 at 16:51
@WimC yes typo, thanks –  xiamx Nov 19 '12 at 16:52

$$\sum_{0 \leq j \leq i \leq n} {n \choose i} {i \choose j}=\sum_{0 \le i \le n} {n \choose i} \sum_{0 \le j \le i}{i \choose j}=\sum_{0 \le i \le n} {n \choose i} 2^i=3^n.$$
Count cardinality of $S = \{(A,B):B \subseteq A \subseteq \left\{1,2,\dots,n\right\}\}$ in two different ways:
Way 1. Each element of $\{1,2,\dots,n\}$ can either be in $A$ and $B$, only in $A$, or in none of $A$ and $B$, so $|S|=3^n$.
Way 2. If $|A|=i$ and $|B|=j$, then there are $n \choose i$ options for $A$ and $i \choose j$ options for $B$, therefore $|S|=\sum_{j \leq i} {n \choose i} {i \choose j}$.