Bài 28 : 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 độ dài n và không có hai số 0 liên tiếp. Có bao nhiêu xâu nhị phân như thế có độ dài bằng 5? Giải Gọi an là số các xâu nhị phân độ dài n và không có hai số 0 liên tiếp. Để nhận được hệ thức truy hồi cho {an] , ta thấy rằng theo quy tắc cộng, số các xâu nhị phân độ dài n và không có hai số 0 liên tiếp bằng số các xâu nhị phân như thế kết thúc bằng số 1 cộng với số các xâu như thế kết thúc bằng số 0. Giả sử n  3.