二項定理

$(a+b)(a+b)\cdots(a+b)$($n$ 個の因子)を展開するとは、各因子から $a$ か $b$ のどちらかを選んで掛け合わせることであり、$a^{n-k}b^k$ の係数は $n$ 個の因子のうち $k$ 個から $b$ を選ぶ方法の数、すなわち $\binom{n}{k}$ に等しい。

$n$ についての帰納法で証明する。基底段階 $n=1$:$(a+b)^1=a+b=\binom{1}{0}a+\binom{1}{1}b$ であり、$\binom{1}{0}=\binom{1}{1}=1$ なので式に一致する。

帰納段階:ある $n$ について式が成り立つ、すなわち $(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k$ と仮定する。両辺に $(a+b)$ を掛けると $(a+b)^{n+1}=\sum_{k=0}^n\binom{n}{k}a^{n+1-k}b^k+\sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1}$ となる。

第二の和を $j=k+1$ で添字変更し、両方の和から $a^{n+1-j}b^j$ の係数を集めると、$0$ から $n+1$ までの各 $j$ について $\binom{n}{j}+\binom{n}{j-1}$ が得られる(規約として $\binom{n}{-1}=\binom{n}{n+1}=0$)。

パスカルの規則 $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ により、この和は $\binom{n+1}{j}$ に等しく、$(a+b)^{n+1}=\sum_{j=0}^{n+1}\binom{n+1}{j}a^{n+1-j}b^j$ となって帰納法が完成する。

二項定理で $a$ と $b$ をともに $1$ とすると、各項 $a^{n-k}b^k$ は $1$ になるので、和全体は項の総数を数えるだけになる。

二項定理 $(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$ 個になる。