乘法原理定理

第一步(基础情形 $k=1$):只有一个步骤时显然有 $N_1 = n_1$ 种方法,与 $k=1$ 时的公式一致。

第二步(基础情形 $k=2$):对完成第1步的 $n_1$ 种方法中的每一种,第2步仍然有 $n_2$ 种做法,因为它的数目不依赖于第1步的结果。这样,所有选择对被分成 $n_1$ 个不相交的组,每组大小为 $n_2$(每种第1步结果对应一组),于是加法原理给出总数为 $n_2$ 自加 $n_1$ 次,即 $N_2 = n_1 \cdot n_2$。

第三步(对 $k$ 归纳):假设公式对 $k-1$ 个步骤成立,即前 $k-1$ 个步骤合起来共有 $N_{k-1}$ 种结果。把这 $k-1$ 个步骤看成一个结果数为 $N_{k-1}$ 的“合成步骤”,把第 $k$ 步看成第二个独立步骤,结果数为 $n_k$(其数目仍不依赖于之前的选择)。对这两步应用两步的基础情形,得到 $N_k = N_{k-1} \cdot n_k$,即 $N_k = n_1 \cdot n_2 \cdots n_k$。由归纳法,该公式对所有 $k$ 都成立。