Quy tắc đếm

Đây là cách phát biểu chặt chẽ cho thói quen đếm riêng từng trường hợp rời nhau rồi cộng lại: điều này đúng chính vì tính rời nhau ngăn không cho bất kỳ kết quả nào bị đếm hai lần.

Bước 1 (trường hợp cơ sở $k=2$): giả sử $A_1$ và $A_2$ rời nhau, tức $A_1 \cap A_2 = \emptyset$. Mỗi phần tử của $A_1 \cup A_2$ thuộc $A_1$ hoặc thuộc $A_2$, và tính rời nhau loại trừ khả năng thuộc cả hai. Chia $A_1 \cup A_2$ thành hai phần rời nhau $A_1$ và $A_2$ rồi đếm mỗi phần một lần cho ta $|A_1 \cup A_2| = |A_1| + |A_2|$.

Bước 2 (quy nạp theo $k$): giả sử công thức đã đúng với $k-1$ tập rời nhau đôi một bất kỳ, tức $|A_1 \cup \cdots \cup A_{k-1}| = |A_1| + \cdots + |A_{k-1}|$. Đặt $B = A_1 \cup \cdots \cup A_{k-1}$. Vì $A_k$ rời với mọi $A_i$ khi $i < k$, nó cũng rời với hợp $B$. Áp dụng trường hợp cơ sở cho $B$ và $A_k$ cho ta $|B \cup A_k| = |B| + |A_k|$.

Bước 3 (kết hợp): thay giả thiết quy nạp cho $|B|$ vào đẳng thức trên, ta được $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_{k-1}| + |A_k|$, đúng là quy tắc cộng cho $k$ tập. Vì trường hợp cơ sở $k=2$ đúng và mỗi bước từ $k-1$ sang $k$ vẫn giữ công thức đúng, nên theo quy nạp công thức đúng với mọi $k \geq 2$.

Vì số lựa chọn ở mỗi bước không phụ thuộc vào các bước trước, nên mọi tổ hợp lựa chọn đều là một kết quả hợp lệ khác nhau, và số tổ hợp nhân lên đúng như đếm số ô trong một lưới hình chữ nhật.

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$.