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?
On
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.
On
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 $$
On
Although the other answers show you how to work your logic into a correct application of the inclusion-exclusion principle, one could take a slightly different approach and sum sizes of nonintersecting sets of events.
Case 1:
First binary digit is 1. Given this condition, all possible strings with attribute fulfill the required 'Or' condition. So there are $2^7$ strings in this set.
Case 2:
The first binary digit is 0. Given this condition, only strings that end in $01$ fulfill the required condition. This leaves only 5 binary digits to freely choose: we count all of the form $0xxxxx01$. So there are $2^5$ strings in this set.
Summing the number of combinations for the two mutually exclusive, but exhaustive conditions yields $2^7 + 2^5$ combinations.
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$.