Number of binary strings of length n with no substrings equal to 0001, 1000 or 1001.

Terms

a(0) =13a(1) =21a(2) =33a(3) =53a(4) =85a(5) =137a(6) =221a(7) =357a(8) =577a(9) =933a(10) =1509a(11) =2441a(12) =3949a(13) =6389a(14) =10337a(15) =16725a(16) =27061a(17) =43785a(18) =70845a(19) =114629a(20) =185473a(21) =300101a(22) =485573a(23) =785673a(24) =1271245a(25) =2056917a(26) =3328161a(27) =5385077a(28) =8713237a(29) =14098313