Vrftsjtryk

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?

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$.

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.

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
$$

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.