部分集合の部分集合の数の和

サイズNの集合に、サイズkの部分集合はいくつあるか→N個からk個選ぶ組み合わせ

$ \sum_{k=0}^N \binom{N}{k} 2^k = \sum_{k=0}^N \binom{N}{k} 2^k 1^{N-k} = (2 + 1)^N= 3^N