Короткий ответ: число таких строк длины $n$ равно $a_n$, где
$$a_0=1,a_1=2,a_n=a_{n-1}+a_{n-2}(n\ge 2),$$ и в закрытой форме
$$a_n=F_{n+2}=\sum _{k=0}^{\lfloor (n+1)/2\rfloor }\left(\genfrac{}{}{0ex}{}{n-k+1}{k}\right),$$ где $F_m$ — числа Фибоначчи ($F_0=0,F_1=1$). Ниже — несколько различных доказательств, сравнение и асимптика.
1) Доказательство рекуррентой (простое, конструктивное).
- Разделим все строки длины $n$ по первой позиции: если первая цифра $0$, оставшиеся $n-1$ позиций могут быть любыми допустимыми — $a_{n-1}$ способов; если первая цифра $1$, то вторая обязательно $0$, и оставшиеся $n-2$ позиции дают $a_{n-2}$ способов. Следовательно
$$a_n=a_{n-1}+a_{n-2},$$ с начальными условиями $a_0=1,a_1=2$. Это даёт $a_n=F_{n+2}$.
2) Комбинаторическое (и эквивалентно включения‑исключения по расположению единиц).
- Считаем по числу единиц $k$. Чтобы $k$ единиц не были смежными, между ними должно быть по крайней мере по одной нулевой «прослойке» (кроме концов). Стандартная биекция даёт число размещений
$$\left(\genfrac{}{}{0ex}{}{n-k+1}{k}\right).$$ Суммируя по $k$ от $0$ до $\lfloor (n+1)/2\rfloor$, получаем
$$a_n=\sum _{k=0}^{\lfloor (n+1)/2\rfloor }\left(\genfrac{}{}{0ex}{}{n-k+1}{k}\right).$$ (Тот же результат можно вывести методом включений‑исключений, учитывая множества позиций пар «11» и устраняя размещения с соседними единицами; итоговая альтернирующая сумма сводится к приведённой биномиальной формуле.)
3) Матричная экспонентация (линейная алгебра, быстрый подсчёт).
- Рекуррентая связь эквивалентна векторному виду
$$\left(\begin{array}{c}{a}_n\\ a_{n-1}\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{a}_{n-1}\\ a_{n-2}\end{array}\right),$$ поэтому
$$\left(\begin{array}{c}{a}_n\\ a_{n-1}\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^{n-1}\left(\begin{array}{c}{a}_1\\ a_0\end{array}\right).$$ Это даёт быстрый алгоритм вычисления за $O(\log n)$ умножений матриц (бинарное возведение в степень). Собственная разложение матрицы даёт формулу Бине:
$$a_n=\frac{{\phi }^{n+2}-{\psi }^{n+2}}{\sqrt{5}},$$ где $\phi =\frac{1+\sqrt{5}}{2},\psi =\frac{1-\sqrt{5}}{2}$.
Сравнение методов.
- Рекуррентный метод — самый простой для доказательства и получения значений по‑порядку (линейное время).
- Комбинаторический подход даёт явную сумму по числу единиц и удобен для точных счётов и понимания структуры строк.
- Метод включений‑исключений формально даёт ту же формулу, но требует аккуратного учёта перекрытий; он хорош, чтобы понять, как исключаются запрещённые локальные паттерны.
- Матричная экспонентация/собственные значения дают быстрый (логарифмический) алгоритм вычисления и сразу асимптику и замыкание (Бине).
Асимптотика.
Из формулы Бине следует
$$a_n\sim \frac{{\phi }^{n+2}}{\sqrt{5}}(n\to \infty ),$$ и отношение последовательных членов стремится к золотовому сечению:
$$\frac{a_{n+1}}{a_n}\to \phi \approx 1.618\dots$$ То есть рост экспоненциальный с базой $\phi$.
Заключение: количество двоичных строк длины $n$ без двух единиц подряд равно $a_n=F_{n+2}$, его можно получить рекурсивно, комбинаторно (или через включения‑исключения) и через матричную экспоненту; асимптотически $a_n\approx {\phi }^{n+2}/\sqrt{5}$.