Number of bitstrings of length 18 that have consecutive 1's — why is my solution wrong?

Question

Consider bitstrings of the pattern 11....(16 dots). There are a total of 2^16 such bitstrings.

Now consider the pattern 011.....(15 dots). It is clear that this pattern and the previous pattern don't overlap, since this one starts with a 0. There are a total of 2^15 such bitstrings.

We can continue upto 000(16 zeros)11.

If we sum them up we get 2^0 + 2^1 + ... + 2^16 = 2^17 - 1 = 131,071.

However, according to the below Python program, the correct answer is 255,379:

m = 0
for k in range(0, 2 ** 18):
   m += '11' in bin(k)

What am I doing wrong?

Answer 1

You have excluded patterns like $01011....$ where the first $1$ is not part of a $11$ sequence.

Answer 2

Since Mark Bennet's response answers the question, it is open season on an alternative response.

I will use recursion to calculate $~R = ~$ the number of $~18~$ character bit strings that do not have consecutive 1's. Then, the final answer will be

$$2^{18} - R.$$

---

For $~n \in \Bbb{Z_{\geq 2}},~$ let

• $~f(n)~$ denote the number of $~n~$ character bit strings that do not have consecutive 1's.

• $~f(n,0)~$ denote the number of $~n~$ character bit strings, whose rightmost character is "0", that do not have consecutive 1's.

• $~f(n,1)~$ denote the number of $~n~$ character bit strings, whose rightmost character is "1", that do not have consecutive 1's.

Then:

• For $~n \in \Bbb{Z_{\geq 2}},~ f(n) = f(n,0) + f(n,1).$

• For $~n \in \Bbb{Z_{\geq 2}},~ f(n+1,0) = f(n).$

• For $~n \in \Bbb{Z_{\geq 2}},~ f(n+2,1) = f(n+1,0) = f(n).$

From the above bullet points, you see that for $~n \in \Bbb{Z_{\geq 2}}$:

• $f(n+2,0) = f(n+1).$

• $f(n+2,1) = f(n).$

• Therefore, $~f(n+2) = f(n) + f(n+1).$

---

So,

• $f(2) = 3.$

• $f(3,1) = f(2,0) = 2,~ f(3,0) = f(2) = 3 \implies $
  $f(3) = 2 + 3 = 5.$

So, you have the fibonacci sequence of

$~3,5,8,13,$
$21,34,55,89,144,$
$233,377,610,987,1597,$
$2584,4181,\color{red}{6765}.$

Therefore, $~R = 6765,~$ and the number of sequences that do have consecutive 1's is

$$2^{18} - R = 262144 - 6765 = 255379.$$