A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have?
I am thinking for the strings that start with a 1, we would have $8 – 1 = 7$ bits to choose, so $2^7$ possible bit strings of length $8$ that starts with a $1$?
Can I go about the second condition the same way and just add the total's together? That is, if my logic is even correct in the first place?
Best Answer
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$.