Question

[Do Kim Khanh]

a) Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi xâu nhị phân độ dài n và không có 3 bít 0 liên tiếp:

Đặt Sn là số chuỗi nhị phân độ dài n, không có 3 bit 0 liên tiếp: Một chuỗi dài n (n≥4) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau: A1 (A là chuỗi có độ dài n - 1, không có 3 bit 0 liên tiếp), gọi số cách là S(n-1) B10 (B là chuỗi có độ dài n - 2, không có 3 bit 0 liên tiếp), gọi số cách là S(n-2) C100 (C là chuỗi có độ dài n - 3, không có 3 bit 0 liên tiếp), gọi số cách là S(n-3) Nên ta có hệ thức truy hồi: Sn=Sn-1 + Sn-2 + Sn-3 Khởi tạo: S1 = 2, S2 = 4, S3 = 7

b) Giải: ??

giúp mình giải hệ thức ở câu a với ạ!