二項係数の和

二項定理 $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$ に $a=1,\ b=1$ を代入すると、左辺は $(1+1)^n=2^n$ となり、右辺は $1$ の任意乗が $1$ であることから $\sum_{k=0}^n\binom{n}{k}1^{n-k}1^k=\sum_{k=0}^n\binom{n}{k}$ となる。

両辺を等しいとおくと、まさに $2^n=\sum_{k=0}^n\binom{n}{k}$ が得られる。

この恒等式には直接的な組合せ的意味もある:$\binom{n}{k}$ は $n$ 個の要素からなる集合 $S$ の $k$ 個の要素からなる部分集合を数えるので、$\sum_{k=0}^n\binom{n}{k}$ は $S$ のあらゆる大きさの部分集合、すなわちべき集合全体を数え、$n$ 個の各要素が独立に部分集合に入るか入らないかであるため、ちょうど $2^n$ 個になる。