Chủ đề này có 2 trả lời

[thinhrost1]

CM: Tập hợp có $n$ phần tử thì sốtậi phợp con của nó là $2^n$

 

[trandaiduongbg]

CM: Tập hợp có $n$ phần tử thì sốtậi phợp con của nó là $2^n$

Có 2 cách chứng minh:

1) Chứng minh trực tiếp 

2) Chứng minh theo quy nạp

 

1)

Chứng minh trực tiếp:

Gọi tập hợp gồm n phần tử là A={x1,x2,...,xn}
Tập con của A chia làm (n+1) loại
- Gồm 0 phần tử: Có C(0,n) tập con
- Gồm 1 phần tử: Có C(1,n) tập con
- Gồm 2 phần tử: Có C(2,n) tập con
...
- Gồm n phần tử: Có C(n,n) tập con
Tổng số tập con là:
X=C(0,n)+C(1,n)+...+C(n,n)
Áp dụng công thức nhị thức NEWTON:
(1+1)ⁿ=C(0,n)+C(1,n)+...+C(n,n)=X(dpcm…

 

2)

Chứng minh bằng quy nạp :

Với n=0 thì số tập hợp con của nó là 1=$2^0$ (tính cả tập rỗng)

Với n=1 thì số tập hợp con của nó là 2=$2^1$ (tính cả tập rỗng)

Giả sử đúng với n=n thì số tập hợp con của nó sẽ là $2^n$ 

Với n=n+1 thì số tập hợp con của nó sẽ là $2^n+2^n$=$2^{n+1}$ (đúng)

Vậy....

Bài viết đã được chỉnh sửa nội dung bởi trandaiduongbg: 15-06-2013 - 17:12

[Nuhoangnam]

e mới lớp 10 có cách giải nào dễ hiểu k ạ