Number of 8-bit binary strings with at least two consecutive 0’s or two consecutive 1’s?

Question

Saw this question while going through Combinatorics, here's my understanding:

For an 8-bit string, $2^8 = 256$ combinations are possible.

Out of these, only two: 01010101 and 10101010 appear to not have either two consecutive 0's or 1's.

Therefore, the answer to the question should be $256 - 2 = 254$.

This question is discussed at https://www.geeksforgeeks.org/n-choose-k-formula/ (Q6) and that page has come to an answer of 492 which is absurd, to say the least.

My explanation for this using combinatorics is,

If we fix digits to 0, starting from index 0 and going to the end (* can be 0 or 1):

00******, we'll have $2^6 = 64$ possibilities
100*****, we'll have $2^5 = 32$ possibilities
1100****, we'll have $2^4 = 16$ possibilities
11100***, we'll have $2^3 = 8$ possibilities
111100**, we'll have $2^2 = 4$ possibilities
1111100*, we'll have $2^1 = 2$ possibilities
11111100, we'll have $2^0 = 1$ possibility

Therefore we'll have $64 + 32 + 16 + 8 + 4 + 2 + 1 = 127$ possibilities.

Now applying the same method and fixing digits to 1, we'll get the same 127 possibilities.

and $127 + 127 = 254$ which matches what my brute force check in Excel shows.

Please poke holes in what I'm thinking here.

Answer 1

Your method gets the correct answer, but the reasoning is wrong, as far as I can tell. For example, when is the string $\texttt{01000000}$ counted by your method?

It's more like this. We break up the strings based on their first occurrence of the string $\texttt{00}$ or $\texttt{11}$. First, let us count the strings whose first occurrence of a doubled digit is $\texttt{00}$. Since there are no earlier doubled digits, everything to the left of the $\texttt{00}$ must alternate between $0$ and $1$.

$\newcommand{\d}{\mathtt x}$There are $2^6$ strings like $\texttt{00******}$.
There are $2^5$ strings like $\texttt{100*****}$.
There are $2^4$ strings like $\texttt{0100****}$.
There are $2^3$ strings like $\texttt{10100***}$.
There are $2^2$ strings like $\texttt{010100**}$.
There are $2^1$ strings like $\texttt{1010100*}$.
There is $2^0$ string like $\texttt{01010100}$.

Add those all up, and you get $64+32+16+8+4+2+1=127$. Then, do the same thing to count the strings whose first occurrence of a doubled digit is $\texttt{11}$. You will get the same numbers, so the final answer is $127+127=254$.

Answer 2

The first digit is 0 or 1. If it is 0, then to avoid two consecutive 0s or 1s the other seven digits must be 1010101. If the first digit is 1, then the others must be 0101010. Therefore exactly two possibilities for not having two consecutive 0s or 1s and 254 for having them.

The 492 that you found is indeed nonsense, as would any answer less than 0 or greater than 255.