乗法の法則(定理)

第1段階(基本ケース $k=1$):手順が1つだけならば明らかに $N_1 = n_1$ 通りであり、$k=1$ のときの公式と一致する。

第2段階(基本ケース $k=2$):手順1を行う $n_1$ 通りの方法それぞれについて、手順2はその結果に関係なくやはり $n_2$ 通りで行える。これにより、選択のすべての組は手順1の各結果に対応する $n_1$ 個の素な、大きさ $n_2$ のグループに分かれるので、加法の法則により合計は $n_2$ を $n_1$ 回足したもの、すなわち $N_2 = n_1 \cdot n_2$ となる。

第3段階($k$ に関する帰納法):公式が $k-1$ 個の手順について成り立つと仮定すると、最初の $k-1$ 個の手順全体で $N_{k-1}$ 通りの結果がある。この $k-1$ 個の手順を $N_{k-1}$ 通りの結果を持つ1つの「合成手順」とみなし、手順 $k$ を $n_k$ 通りの結果を持つ独立した2番目の手順とみなす(その数は前の選択に依存しない)。この2手順に基本ケースを適用すると $N_k = N_{k-1} \cdot n_k$、すなわち $N_k = n_1 \cdot n_2 \cdots n_k$ が得られる。帰納法によりこの公式はすべての $k$ で成り立つ。