Cách tính số tập hợp con có n phần tử?

Ta đặt : A là một tập hợp có n phần tử

Số tập hợp con của A gồm n phần tự là 2ⁿ

Thật vậy, bằng phương pháp qui nạp ta có :

• Với n = 0, tập hợp rỗng có 2⁰ = 1 tập hợp con (đúng)

• Với n = 1, 2¹ = 2 tập hợp rỗng và chính nó (đúng)

Giả sử công thức trên đúng với n = k. Tức số tập hợp con của một tập hợp là 2^k

Ta phải chứng minh công thức đúng với k + 1

Ngoài 2^k  tập hợp con vốn có, thêm mỗi tập hợp cũ phần tử thứ k + 1 thì được một tập hợp con mới. Vậy ta được 2^k tập hợp con mới.

Tổng số tập hợp con của tập hợp gồm k + 1 phần tử (tức tổng số tập hợp con của tập hợp gồm 2^k phần tử và tập hợp con mới tạo thành) là : 2^k  = 2^k .2 = 2^{k + 1}.

Vậy số tập hợp con của tập hợp A gồm n phần tử là 2ⁿ.