Tìm hệ thức truy hồi và điều kiện đầu để tính số xâu nhị phân độ dài n bit luôn chứa hai bít 1 liên tiếp.

Tìm hệ thức truy hồi và điều kiện đầu để tính số xâu nhị phân độ dài n bit luôn chứa hai bít 1 liên tiếp.
Giải



Một số có 2 bít 1 kề nhau có 3 dạng sau:
A11 (A bất kì độ dài $n-2$ , số trường hợp là $2^{n-2}$)
B01 (B chứa 2 bit 1 kề nhau dài $n-2$ có $a_{n-2}$)
C0 (C chứa 2 bit 1 kề nhau dài $n-1$ có $a_{n-1}$)

Vậy $a_n=a_{n-1}+a_{n-2}+2^{n-2}$
Điều kiện đầu $a_0=0;a_1=0$