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$

  • 3
    $\begingroup$ $2 = 1+1$. :-) Also, shouldn't it be $j \leq i$? $\endgroup$ – WimC Nov 19 '12 at 16:51
  • $\begingroup$ @WimC yes typo, thanks $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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