Chứng minh với một tập hợp có n phần tử thì sẽ cí 2^n tập hợp con
Minh họa :
A = { 1;2;3;…;n)
CMR : Số tập hợp con của A là 2^n
Chứng minh với một tập hợp có n phần tử thì sẽ cí 2^n tập hợp con
Minh họa :
A = { 1;2;3;…;n)
CMR : Số tập hợp con của A là 2^n
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 tập con (đúng)
Với n = 1, ta có 2^1=2 (tập rỗng và chính nó) ⇒ đúng
Giả 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 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=2^(k+1)(đúng)
Vậy số tập con của tập A gồm n phần tử là 2^n