А теперь будем рассуждать логически-математически:
k(x) - функция количества чисел содержащих '11'
k(0)=0
k(1)=0
k(2)=1
11
k(3)=3
11 - число пришедшее от предыдущей разрядности
110 - числа полученный добавлением в начало '11' и перебором
111 - остальных свободных бит т.е. вида 11x
k(4)= 8
11
110
111
1011
1100
1101
1110
1111
С первыми 3-мя числами все ясно, они пришли от предыдущей разрядности. Последние четыре, то же ясны, они вида 11xx.
И остаеться одно интересное число - 1011, будем условно называть такие числа - числа Лакмусачи (Lukmusacci) ))).

k(5)=19
Количество складываеться из:
-8 чисел от предыдущей разрядности
-8 чисел вида 11xxx
-3 числа Лакмусачи

k(6)=43
Количество складываеться из:
-19 чисел от предыдущей разрядности
-16 чисел вида 11xxxx
-8 чисел Лакмусачи

Пронзительный читатель уже догадался к чему я виду:
количество чисел Лакмусачи для разрядности n равно k(n-2) , посмотрите внимательно Лакмусачи для 6 равно количеству чисел содержащих '11' для 4.

В итоге мы можем вывести эмпирическую функцию k(n):
k(n)=k(n-2)+k(n-1)+2^(n-2), где k(n-2) - числа Лакмусачи,
k(n-1) - числа пришедшие от прошлой разрядности, 2^(n-2) - числа вида 11x.
Тем самым количество чисел не содержащих '11' для разрядности n равно: 2^(n) - k(n)=2^(n)-k(n-2)-k(n-1)-2^(n-2)