Probar

Question

Cómo probar $3^n = \sum{0 \leq j \leq i \leq n} n \choose i i \choose j$usando$3^n = \sum{0 \leq i \leq n} 2^in \choose i$

Answer 1

ps

Answer 2

Cuenta cardinalidad de $S = {(A,B):B \subseteq A \subseteq \left{1,2,\dots,n\right}}$ de dos formas diferentes:

Forma 1. Cada elemento de ${1,2,\dots,n}$ puede ser en $A$ y $B$, sólo en $A$, o ninguno de $A$ y $B$, que $|S|=3^n$.

Way 2. Si $|A|=i$ y $|B|=j$, entonces hay $n \choose i$ opciones para $A$ opciones de y $i \choose j$ $B$, por lo tanto $|S|=\sum_{j \leq i} {n \choose i} {i \choose j}$.