Xét tập A có n phần tử
Ta sẽ đếm số tập con của chúng bằng hai cách:
-Cách 1:
+Số tập con có 0 phần tử là: \(C^0_n\) tập
+Số tập con có 1 phần tử là: \(C^1_n\) tập
...
+Số tập con có 0 phần tử là: \(C^n_n\) tập
Khi đó vế trái của đẳng thức cần chứng minh là tổng số tập con của tập đó
Cách 2: Xét tập B là tập con của tập A
Một phần tử i bất kì thuộc A có thể thuộc B hoặc không thuộc B nên phần tử i đó có 2 khả năng xảy ra. Làm tương tự với n-1 phần tử còn lại thì vế phải của đẳng thức cần chứng minh là số tập con của tập A
Ta chứng minh bằng quy nạp.
Ta thấy công thức trên đúng với n = 1.
Giả sử nó đúng đến n. Ta chứng minh nó đúng với n + 1.
Nhận thấy VT là số tập hợp con của một tập hợp có n phần tử.
Nếu ta thêm 1 phần tử thì số tập hợp con tăng thêm chính bằng số tập hợp con của tập hợp đó.
Do đó số tập hợp con của một tập hợp có n + 1 phần tử là: \(2^n+2^n=2^{n+1}\).
Vậy công thức trên đúng với n + 1. Phép cm hoàn tất.
