Tổng quát: Cho tập [tex]A=\left \{ 1;2;3;...;n \right \}[/tex] . Tính số tập con của $A$ khác rỗng sao cho không có 2 số nguyên liên tiếp nào
Xét tập con có $k$ phần tử thỏa mãn yêu cầu đề [tex]\left \{ a_1;a_2;...;a_k \right \}[/tex]
Ta có: [tex]1\leq a_1< a_2-1< ...< a_k-k+1< n-k+1[/tex]
Có [tex]C_{n-k+1}^{k}[/tex] tập con như vậy
Số tập con cần tìm là: [tex]S=\sum_{k=1}^{\left [ \frac{n+1}{2} \right ]}C_{n-k+1}^{k}=F_{n+2}-1[/tex]
p/s: [tex]F_{n+2}[/tex] là dãy Fibonacci
Bạn tự tính nhé