Câu 15. Tìm hệ thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân có độ dài n và không có 2 số 0 liên tiếp. Có bao nhiêu xâu nhị phân như thế có độ dài bằng 4

Để tìm hệ thức truy hồi cho số các xâu nhị phân có độ dài n và không có 2 số 0 liên tiếp, ta gọi số lượng xâu nhị phân này là \( a_n \). Hệ thức truy hồi được xây dựng như sau: - Nếu xâu nhị phân có độ dài n kết thúc bằng 1, thì phần còn lại của xâu (độ dài n-1) có thể là bất kỳ xâu nào không có 2 số 0 liên tiếp, tức là có \( a_{n-1} \) xâu. - Nếu xâu nhị phân có độ dài n kết thúc bằng 0, thì bit thứ n-1 phải là 1 (để không có 2 số 0 liên tiếp), và phần còn lại của xâu (độ dài n-2) cũng có thể là bất kỳ xâu nào không có 2 số 0 liên tiếp, tức là có \( a_{n-2} \) xâu. Vì vậy, ta có hệ thức truy hồi: \[ a_n = a_{n-1} + a_{n-2} \] Điều kiện đầu là: - \( a_1 = 2 \) (các xâu: "0", "1") - \( a_2 = 3 \) (các xâu: "00", "01", "10", "11") Để tính số xâu nhị phân có độ dài bằng 4, ta tính như sau: - \( a_3 = a_2 + a_1 = 3 + 2 = 5 \) - \( a_4 = a_3 + a_2 = 5 + 3 = 8 \) Vậy có 8 xâu nhị phân có độ dài bằng 4 và không có 2 số 0 liên tiếp.