# 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\;.$$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}