Number of binary strings of length 8 that contain either three consecutive 0s or four consecutive 1s

How many bit strings (Consists of only 0 or 1) of length 8 contain either three consecutive 0s or four consecutive 1s?

I am getting answer 256 but the provided answer is 147 . Can anyone explain why it is 147?

Attempt

Case 1. Let's take 3 zeros as a single unit. They can be placed in 6 positions (2 sides positions and 4 positions in between 5 elements) rest of the five elements can be selected in $2^5$ ways (they can either be 0 or 1). So total $n_1=6\cdot 2^5$ but here you can have 8 ways to get 4 consecutive 1s..

In same way for Case 2. $n_2$ will be $5\cdot 2^4$ and here also we can find 8 ways to get 3 consecutive 0s. Thus total $= n_1+n_2-(8+8)=272-16=256$.

Lets use inclusion-exclusion method.

First we find the number of bit-strings from size of $n$ that doesn't contain the sequence '000'. We will construct recursion formula, let $F(n)$ be that number.

• If the first bit is '1' then the rest is just a string that doesnt contain '000' from size $n-1$
• If the first bits is '01' then the rest is just a string that doesnt contain '000' from size $n-2$
• If the first bit is '001' then the rest is just a string that doesnt contain '000' from size $n-2$

Therfore we get: $F(n) = F(n-1)+F(n-2)+F(n-3)$

With the initial conditions $F(0) =1, F(1) =2, F(2) =2^2$

With te same method we get: $G(n) = G(n-1)+G(n-2)+G(n-3)+G(n-4)$

With the initial conditions $G(0) =1, G(1) =2, G(2) =2^2, G(3)=2^3$

Where $G(n)$ is the number of bit-strings from size of $n$ that doesn't contain the sequence '1111'.

Now, by opening the recursion up we get $F(8)= 149$ and $G(8)=208$

So if we define:

• A = bit-string of size 8 that contain '000'
• B = bit-string of size 8 that contain '1111'

and by what we calculated we have $|A| = 2^8-F(8)$ and $|B| = 2^8-G(8)$

What left to complete inclusion exclusion is to find the size of $|A\cap B|$, which is easy since the only strings that satisfy both are: '00001111' , '11110000', '11111000', '00011111', '00011110', '10001111', '01111000', '11110001'

Now the desiered number is $|A|+|B|-|A \cap B|$