Tim Cong Thuc Truy Hoi

Đề bài Tìm hệ thức truy hồi cho số các xâu nhị phân có độ dài n không chứa 3 số 0 liên tiếp

Giải Gọi số xâu nhị phân có độ dài là n ko chứa 3 số 0 liên tiếp là An Ta có An-1 là số xâu có dạng xxxxxxxx1 An-2 là số xâu có dạng xxxxxxx10 An-3 là số xâu có dạng xxxxxx100 Ta có An = An-1 + An-2 + An-3 Vậy hệ thức truy hồi là

An = An-1 + An-2 + An-3

Nhưng nếu giải cụ thể để tìm ra công thức thì phải giải phương trình bậc 3 Mà phương trình bậc 3 này chỉ có 1 nghiệm,vậy thì làm thế nào Phương trình bậc 3 nè x3 − x2 − x − 1 = 0 Phương trình này có 1 nghiệm thì làm thế nào bây giờ