Qfyilyi

How many bit strings of length 10 either begin with three 0s or end with two 0s?

I solved this question using cases but I do not seem to be getting the answer of $352$.

My attempt:
Consider two cases:

• Case 1: The string begins with three $0$s and does not end with two $0$s. There is only $1$ way to choose the first three bits, $2^5$ ways for the middle bits, and $3$ ways for the last two bits ($4$ ways to construct a string of two bits, minus $1$ way to make three $0$s). There are $2^5 cdot 3$ ways to construct strings of this type.


• Case 2: The string does not begin with three $0$s but ends with two $0$s. There are $2^3 - 1 = 7$ ways to choose the first three bits without three $0$s, $2^5$ ways for the middle bits, and $1$ way for the last two bits. There are $7 cdot 2^5$ ways to construct strings of this type.

By the rule of sum, there are $2^5 cdot 3 + 2^5 cdot 7 = 320$ ways to construct bit strings of length 10 either begin with three $0$s or end with two $0$s.

You are missing the strings that both begin with three zeroes and end with two zeroes.

And since there are five bits left that can be anything, you have $2^5=32$ of those, exactly the difference

$$underbrace{2^7}_{text{begin with three zeros}}+underbrace{2^8}_{text{end with two zeros}}-underbrace{2^5}_{text{double-count}} $$