Number of length n binary words that contain 111 but do not contain 000 (as contiguous subwords).

Terms

a(0) =0a(1) =0a(2) =0a(3) =1a(4) =3a(5) =8a(6) =18a(7) =39a(8) =81a(9) =164a(10) =326a(11) =639a(12) =1239a(13) =2382a(14) =4548a(15) =8635a(16) =16319a(17) =30722a(18) =57650a(19) =107885a(20) =201425a(21) =375322a(22) =698162a(23) =1296801a(24) =2405707a(25) =4457984a(26) =8253228a(27) =15266969a(28) =28220967a(29) =52134000