Chứng minh rằng : Nếu tập `A` có `n` phần tử thì số tập con của `A` là `2^(n)`. (Chứng minh bằng qui nạp)

Cách dùng quy nạp :

Xét `n = 1` thì tập `A` có 2 tập con là tập rỗng và chính đó

Giả sử với `n = k (k > 1)` thì tập `A` có `2^k` tập con (*)

Và giả sử `A = {a_1 ; a_2 ; ... ; a_k}`

Xét `n = k + 1` thì tập `A` có thêm một phần tử nữa và ta đặt phần tử đó là `a_(k+1)`

Thì A sẽ có thêm `2^k` tập con nữa được lấy từ các tập của (*) và thêm phần tử `a_(k+1)`

Như vậy A sẽ có tổng cộng : `2^k + 2^k = 2^(k + 1)` tập con

Theo quy nạp ta có điều phải chứng minh

-----------------------------------

Cách không dùng quy nạp :

- Số cách chọn ra tập con có 0 phần tử từ tập A là : `C_n^0` cách

- Số cách chọn ra tập con có 1 phần tử từ tập A là : `C_n^1` cách

.....

- Số cách chọn ra tập con có n phần tử từ tập A là : `C_n^n` cách

Theo quy tắc cộng có : `C_n^0 + C_n^1 + .... + C_n^n`

`= (1 + 1)^n`

`= 2^n` cách chọn

Vậy tập `A` có `2^n` tập con