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$.
$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}$.
The Fibonacci numbers are defined recursively, but the linked article gives closed forms. Perhaps the most convenient for computation is
$$F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\;,$$
where $$\varphi=\frac{1+\sqrt5}2\;.$$
