How many numbers from 1 to 2^n have '11' as a substring in binary representation?

Question

For example: say $n = 2$. The numbers from $1$ to $2^2$ are $1, 2, 3, 4$. i.e. $1, 10, 11, 100$ in binary. So the result is $1$, because only one number i.e. $3$ is there such that it has 11 in it.

For $n = 3$, $3, 6, 7$ have '11', so the result is $3$.

Answer 1

Let $E_n$ be the set of integers between $1$ and $2^n$ for which $11$ doesn't appear in the binary representation. If $k$ is such a number, then either

• The binary representation of $k$ starts with $0$, i.e. $k \in E_{n-1}$, or
• The binary representation of $k$ starts with $10$ (can't be $11$ of course), and the rest is an arbitrary string of $n-2$ digits with no $11$, i.e. $k - 2^{n-1} \in E_{n-2}$

The above actually describes a one to one mapping between $E_n$ and $E_{n-1} \sqcup E_{n-2}$ , where $\sqcup$ represents a disjoint union. From this we get $|E_n| = |E_{n-1}| + |E_{n-2}|$. Noting $|E_2| = 3$ and $|E_1| = 2$, we finally have $|E_n| = Fib(n+2)$, where $Fib$ is the Fibonnaci sequence.

Back to your original question, the answer is now obviously $2^n - |E_n|$ = $2^n - Fib(n+2)$