1/ Tính số tập con của $ \left \{ 1,2,...,n \right \} $ không chứa 2 số liên tiếp.
Trước hết, ta tính số tập con của $\left \{ 1,2,3,...,n \right \}$ có đúng $k$ số và không chứa 2 số liên tiếp.
Giả sử $k$ số đó là $x_{1},x_{2},x_{3},...,x_{k}$ thỏa mãn $1\leqslant x_{1}< x_{2}< x_{3}<...< x_{k}\leqslant n$
với $\left | x_i-x_j \right |\geqslant 2$
Đặt $a_{i}=x_{i}-(i-1)$ suy ra $1\leqslant a_1< a_2< a_3<...< a_k\leqslant n-k+1$
Số cách chọn $k$ số từ tập đã cho chính là số cách chọn $k$ số $a_{i}$ và bằng $C_{n-k+1}^{k}$
Vậy số tập con có đúng $k$ số và không chứa 2 số liên tiếp là $C_{n-k+1}^{k}$.
$\Rightarrow$ số tập con không chứa 2 số liên tiếp là $\sum_{k=0}^{\left \lfloor \frac{n+1}{2} \right \rfloor}C_{n-k+1}^k$