wannable

ta

Số tập con của $ \left \{ 1,2,...,n \right \} $không chứa 2 số nguyên dương liên tiếp cũng chính là số xâu nhị phân kích thước n
không có 2 bit 1 liên tiếp. Gọi $S_{n}$ là số xâu nhị phân kích thước n có tính chất như thế thì ta có : $S_{1}=2; S_{2}=3$ và $S_{n}= S_{n-1}+ S_{n-2}$ với $ n\geq 3$. Đây là hệ thức truy hồi tính số Fibonacci nên ta có số tập con thỏa yêu cầu đề bài là :
$S_{n}=F_{n+2}=\frac{\varphi ^{n+2}-\psi ^{n+2}}{\sqrt5}$
với $\varphi =\frac{1+\sqrt5}{2}$ và $\psi =\frac{1-\sqrt5}{2}$

 

tại sao S1=2 ạ