How many bit strings of length 8 start with "1" or end with "01"?

Solution 1:

We interpret starts with $1$ or ends in $01$ as meaning that bit strings that satisfy both conditions qualify.

By your correct analysis, there are $2^7$ bit strings that start with $1$.

Similarly, there are $2^6$ bit strings that end with $01$.

The sum $2^7+2^6$ double-counts the bit strings that start with $1$ and end with $01$.

There are $2^5$ of these, so there are $2^7+2^6-2^5$ bit strings that start with $1$ or end with $01$.

Solution 2:

The strategy you seem to be proposing is to note that there are $2^7$ bit strings starting with $1$ and $2^6$ ending with $01$, since one may make $7$ choices in the first case and $6$ choices in the second. If we add these up to get $2^6+2^7$, this doesn't quite work to count the number of strings satisfying either condition. In particular, consider a string like $$10000001$$ it both starts with $1$ and ends with $01$, so the above method would have counted it twice. In particular, the remedy for this is to subtract out the number of strings that satisfy both conditions from the sum $2^6+2^7$ to compensate for counting those strings twice.

This is the inclusion-exclusion principle.

Solution 3:

Here is another way to arrive at the answer, without doing the whole "double count and then correct for it" dance:

Of all possible octets (8-bit strings), half of them will begin with $1$. Of the other half (i.e. those that begin with $0$), a quarter will end with $01$. Since there are $2^8$ possible octets, we have: $$ 2^8 \times \frac{1}{2} + 2^8 \times \frac{1}{2} \times \frac{1}{4} \\ 2^7 + 2^5 $$ While this may not look identical to the other answers, note that: $$ 2^5 = 2^6 - 2^5 $$ because $$ 2^6 - 2^5 = 2 \times 2^5 - 2^5 = 2^5 + 2^5 - 2^5 = 2^5 $$