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$
Prove $3^n = \sum_{0 \leq i \leq j \leq n} $ $ n \choose i$ $ i \choose j$
5
$\begingroup$
combinatorics
binomial-coefficients
-
0@WimC yes typo, thanks – 2012-11-19
2 Answers
12
$ \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. $
7
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}$.