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

Terms

a(0) =14a(1) =25a(2) =45a(3) =82a(4) =150a(5) =275a(6) =505a(7) =928a(8) =1706a(9) =3137a(10) =5769a(11) =10610a(12) =19514a(13) =35891a(14) =66013a(15) =121416a(16) =223318a(17) =410745a(18) =755477a(19) =1389538a(20) =2555758a(21) =4700771a(22) =8646065a(23) =15902592a(24) =29249426a(25) =53798081a(26) =98950097a(27) =181997602a(28) =334745778a(29) =615693475