How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?

336 Views Asked by At

I have this post here for the same question, but I will present different answer and state where my issue is.

For the question, we can see that for 3 consecutive 0s, we can divide answer to different cases:

  1. 3 consecutive bits come at the beginning, we have $2^5$ different possibilities.
  2. The first 0 bit came in the 2nd place, we have $2^4$ different possibilities as the first bit can not be both 0 and 1.
  3. The first 0 bit came in the 3nd place, we have $2^4$ different possibilities and the first bit before 0 must be 1.
  4. The first 0 bit came in the 4th place, we have $2^4$ different possibilities and the first bit before 0 must be 1.

Problem: In case of the first bit come at 5th position, the first bit before 0 must be 1 and the first bit of the 8 bits must be 1 as well as if it was 0, we would have duplicate since we calculated that in case 1 above, where we have $2^5$. So the answer is $2^3$ in my attempt, but the solutions says $2^3 - 1$, so can you please explain why we have $2^3 - 1$ and not $2^3$ in the answer?

$$1 2 2 1 0 0 0 2 = 2^3$$