Bài toán 3. Chứng minh số tập con thực sự và khác rỗng của một tập có n phần tử là ${{2}^{n}}-1$
Cho tập $S$ có $n$ phần tử thì số tập con của $S$ là $2^{n}$ (kể cả tập rỗng)
Bài toán trên chứng minh bằng nguyên lý quy nạp
Chứng minh:
Bước 1: $n=1\Rightarrow$ tập $S$ có $2$ tập con là chính nó và tập rỗng.
Bước 2: Giả sử $n=k$ thì số tập con của $S$ là $2^{k}$
Bước 3:Ta cần chứng minh với $n=k+1$ thì số tập con của $S$ là $2^{k+1}$
Đặt $A=\begin{Bmatrix} a_{1};a_{2};...;a_{k} \end{Bmatrix}$ và $B=\begin{Bmatrix} a_{1};a_{2};...;a_{k};a_{k+1} \end{Bmatrix}$
Do $A\subset B$ nên số tập con của B là:
* Các tập con của A có $2^{k}$ tập
* Các tập con của A thêm phần tử $a_{k+1}$ ta có: $2^{k}$ tập
Dẫn đến số tập con của tập có $k+1$ phấn tử là $2^{k+1}$ tập
Do đó số tâp con của tập có $n$ phần tử là $2^{n}$ tập
Vậy số tập con của tập có $n$ phần tử và khác rỗng là $2^{n}-1$ tập