Số tập con của tập hợp A gồm n phần tử là 2^n
Với n = 0, tập rỗng có 2 0 = 1 20=1 tập con (đúng)
Với n = 1, ta có 2 1 = 2 21=2 (tập rỗng và chính nó) =>đúng
Gỉa sử công thức đúng với n = k, nghĩa là số tập con của tập hợp gồm k phần tử là 2^k
Cần chứng minh công thức đúng với n = k+1
Ngoài 2^k tập con đã có, ta thêm vào mỗi tập cũ phần tử thứ k+1 thì được một tập con mới. Vậy ta được 2 k 2k tập con mới. Tổng cộng ta có số tập con của tập hợp gồm k+1 phần tử là: 2^k + 2^k=2. 2 k 2k= 2 k + 1 2k+^1(đúng) Vậy số tập con của tập A gồm n phần tử là 2 n
