数え上げの原理

これは、互いに重ならない各場合を別々に数えて足すという日常の直感を厳密にしたものである。素であることが、どの結果も二重に数えられないことを保証するからこそ成り立つ。

第1段階(基本ケース $k=2$):$A_1$ と $A_2$ が素であるとする、つまり $A_1 \cap A_2 = \emptyset$。$A_1 \cup A_2$ の各要素は $A_1$ か $A_2$ のいずれかに属し、素であることから両方に属することはない。$A_1 \cup A_2$ を素な2つの部分 $A_1$ と $A_2$ に分けてそれぞれを1回数えると $|A_1 \cup A_2| = |A_1| + |A_2|$ が得られる。

第2段階($k$ に関する帰納法):任意の $k-1$ 個の互いに素な集合について公式がすでに成り立つ、すなわち $|A_1 \cup \cdots \cup A_{k-1}| = |A_1| + \cdots + |A_{k-1}|$ と仮定する。$B = A_1 \cup \cdots \cup A_{k-1}$ とおく。$A_k$ は $i < k$ を満たすすべての $A_i$ と素なので、それらの和集合 $B$ とも素である。基本ケースを $B$ と $A_k$ に適用すると $|B \cup A_k| = |B| + |A_k|$ が得られる。

第3段階(結合):この等式に帰納法の仮定 $|B|$ を代入すると $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_{k-1}| + |A_k|$ が得られ、これはまさに $k$ 個の集合に対する加法の法則である。基本ケース $k=2$ が成り立ち、$k-1$ から $k$ への各段階で公式が保たれるので、帰納法によりすべての $k \geq 2$ で成り立つ。

各手順の選択肢の数が前の手順に依存しないため、選択の組み合わせはすべて異なる正当な結果となり、その組み合わせ数はちょうど長方形の格子のマス目を数えるのと同じように積になる。

第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$ で成り立つ。