Định lý quy tắc nhân

Bước 1 (trường hợp cơ sở $k=1$): với một bước duy nhất, hiển nhiên có $N_1 = n_1$ cách, khớp với công thức khi $k=1$.

Bước 2 (trường hợp cơ sở $k=2$): với mỗi trong $n_1$ cách thực hiện bước 1, bước 2 vẫn có thể thực hiện theo $n_2$ cách, vì số cách của nó không phụ thuộc vào kết quả bước 1. Điều này chia mọi cặp lựa chọn thành $n_1$ nhóm rời nhau, mỗi nhóm cỡ $n_2$ (một nhóm ứng với mỗi kết quả bước 1), nên quy tắc cộng cho tổng là $n_2$ cộng với chính nó $n_1$ lần, tức $N_2 = n_1 \cdot n_2$.

Bước 3 (quy nạp theo $k$): giả sử công thức đúng với $k-1$ bước, tức $k-1$ bước đầu cùng nhau có $N_{k-1}$ kết quả. Coi $k-1$ bước đó như một "siêu bước" gộp lại có $N_{k-1}$ kết quả, và bước $k$ là bước độc lập thứ hai có $n_k$ kết quả (số cách của nó vẫn không phụ thuộc các lựa chọn trước). Áp dụng trường hợp cơ sở hai bước cho cặp này cho ta $N_k = N_{k-1} \cdot n_k$, tức $N_k = n_1 \cdot n_2 \cdots n_k$. Theo quy nạp, công thức đúng với mọi $k$.