CM: Tập hợp có $n$ phần tử thì sốtậi phợp con của nó là $2^n$
CM: Tập hợp có $n$ phần tử thì sốtậi phợp con của nó là $2^n$
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
e mới lớp 10 có cách giải nào dễ hiểu k ạ
0 thành viên, 0 khách, 0 thành viên ẩn danh