二項定理

$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$ となって帰納法が完成する。