Tìm công thức tổng quát tính số tập hợp con của 1 tập hợp. ( theo cách quy nạp )
Tìm công thức tổng quát tính số tập hợp con của 1 tập hợp. ( theo cách quy nạp )
#1
Đã gửi 26-09-2016 - 20:44
#2
Đã gửi 08-07-2017 - 18:19
#3
Đã gửi 09-07-2017 - 07:47
Tập có n phần tử thì có $2^{n}$ tập con.
Sự khác biệt giữa thiên tài và kẻ ngu dốt là ở chỗ thiên tài luôn có giới hạn.
#4
Đã gửi 12-07-2017 - 23:13
Ta xét tập rỗng trước. Tập này có đúng một tập con là chính nó.
Tiếp theo xét một tập có đúng $1$ phần tử. Tập này có đúng $2$ tập con là tập rỗng và chính nó.
Xét tập có hai phần tử $\{a,b\}$. Tập này có đúng $4$ tập con là $\varnothing, \{a\}, \{b\}, \{a,b\}$.
Dự đoán rằng tập có $n$ phần tử thì có đúng $2^n$ tập con. Chứng minh: Giả sử khẳng định của ta là đúng với trường hợp $n=k$ nguyên dương nào đó. Ta sẽ chứng minh điều đó đúng với $n=k+1$. Thật vậy, xét tập $S$ có $k+1$ phần tử. Gọi $x$ là một phần tử bất kỳ của $S$. Rõ ràng các tập con của $S$ đều có thể xếp vào đúng một trong hai lớp:
- Lớp thứ nhất gồm các tập con của $S\setminus \{x\}$, tức là không chứa $x$. Rõ ràng lớp này có $2^k$ phần tử theo giả thuyết quy nạp.
- Lớp thứ hai gồm các tập con của $S$ mà chứa $x$. Các tập này lại có dạng $T\cup \{x\}$ với $T$ là tập con của $S$ thuộc lớp thứ nhất. Vậy lớp này cũng sẽ có đúng $2^k$ phần tử.
Vậy tóm lại là $S$ có đúng $2^k+2^k=2^{k+1}$ tập con, chứng tỏ khẳng định của ta là đúng với mọi $n$ nguyên dương. $\square$
- dungxibo123 và Sin99 thích
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh