Решить задачу

Давай попробуем вместе решить эту задачу. Мы должны найти количество последовательностей длины 12, которые состоят только из нулей и единиц, и в которых встречаются две подряд идущие единицы.

Как мы можем подойти к этой задаче? Сначала давай заметим, что любая такая последовательность может начинаться либо с 0, либо с 11, так как если начать с 1, то следующей цифрой должна быть 1 (чтобы удовлетворить условию про две подряд идущие единицы).

Теперь задачу можно решить методом рекурсивных соотношений. Подсчитаем количество последовательностей длиной n, оканчивающихся на 0 и на 11:

1. Если последовательность оканчивается на 0, то перед нулём может идти любая последовательность длины n-1.
2. Если последовательность оканчивается на 11, то перед этими единицами обязательно должен идти 0, таким образом перед тройкой "011" может идти любая последовательность длины n-3.

Обозначим количество подходящих последовательностей длины n, которые оканчиваются на 0, через a_n, и количество подходящих последовательностей, которые оканчиваются на 11, через b_n.

Тогда можно записать следующие соотношения: a_n = a_{n-1} + b_{n-1} b_n = a_{n-2}

Так как a_{n-2} = a_{n-3} + b_{n-3}, то можем переделать в