# How many numbers from $1$ to $2^n$ will have $11"$ as substring in binary representation?

For example say, $n = 2$. So our set is $\{1, 2, 3, 4\}$ in base $10$ and $\{1, 10, 11, 100\}$ in base $2$. So Output $1$, because only one number i.e. $3$ is there such that it has $11"$ in it.

For $n = 3$, we get $\{3, 6, 7\}$ as having $11"$, so output $3$.

• The binary representation will have at least $1$ and at most $n+1$ digits, the latter one being $2^n$. So count the appearances of $11$ in strings with length $\in \{2,...n\}$. – Alp Uzman Feb 9 '15 at 17:54
• That will be so much computation. – user123 Feb 9 '15 at 17:56
• Not really: for strings of $k$ digits there are $(k-1)!2^{k-2}$ for which $11$ appears at least once. – Alp Uzman Feb 9 '15 at 18:01
• @Uzman: That formula is incorrect. For $k=3$ it gives $4$, but the correct number is $3$. – Brian M. Scott Feb 9 '15 at 18:04
• Oh yes, my formula overcounts. Thanks. – Alp Uzman Feb 9 '15 at 18:07

$2^n$ does not. All of the other integers in the given range can be written as $n$-bit strings, with leading zeroes as needed. Thus, you want the number of $n$-bit strings that have two adjacent ones. It’s actually easier to count those that do not have two adjacent ones and subtract from $2^n$. That problem is solved in this question and answer: there are $F_{n+2}$ such sequences, where $F_n$ is the $n$-th Fibonacci number. The number that you want is therefore $2^n-F_{n+2}$.
$$F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\;,$$
where $$\varphi=\frac{1+\sqrt5}2\;.$$