Hằng đẳng thức Pascal

Bước 1 (cố định một phần tử và tách theo việc có chứa nó hay không): cố định một đối tượng $x$ trong $n$ đối tượng. Mỗi tập con $k$ phần tử hoặc chứa $x$ hoặc không chứa; hai trường hợp này rời nhau và cùng nhau phủ hết $C_n^k$ tập con.

Bước 2 (đếm tập con chứa x): một tập con chứa $x$ được tạo bằng cách chọn $k-1$ phần tử còn lại từ $n-1$ đối tượng kia, cho $C_{n-1}^{k-1}$ tập con như vậy.

Bước 3 (đếm tập con không chứa x): một tập con không chứa $x$ được tạo bằng cách chọn cả $k$ phần tử từ $n-1$ đối tượng còn lại, cho $C_{n-1}^k$ tập con như vậy.

Bước 4 (áp dụng quy tắc cộng): vì hai trường hợp rời nhau và phủ hết mọi tập con cỡ k, quy tắc cộng cho $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$.