Question

Рассмотрим алфавит из 2 букв. словом будем считать любое конечное сочетание букв. назовём слово непроизносимым, если в нём встречается больше двух одинаковых букв подряд. на сколько больше произносимых 10 буквенных слов, чем 9-буквенных?

Answer 1

Произносимые слова - это слова, в которых имеется не более двух одинаковых букв подряд. Пусть алфавит состоит из букв "0" и "1".
Обозначим $F_n$ - количество произносимых слов длины n, начинающихся с 1. Очевидно, количество произносимых слов, начинающихся с 0 также равно $F_n$ (одни получаются из других взаимной заменой 0 и 1). Тогда, если n≥3, то любое произносимое слово длины n, начинающееся с 1, можно получить одним из следующих двух
1) К "1" приставить справа любое произносимое слово длины n-1, начинающееся на 0. Таких слов  $F_{n-1}$ штук, причем, полученные слова обязательно будут произносимыми, т.к. начинаются на "10" и не могут содержать три нуля или три единицы подряд.
2) К "11" приставить справа любое произносимое слово длины n-2, начинающееся на 0. Таких слов  $F_{n-2}$ штук. Это слово также произносимо, т.к. начинается на 110, и, значит, не содержит трех нулей или единиц подряд.
Итак, $F_{n}=F_{n-1}+F_{n-2}$ и легко видеть, что $F_{1}=1$ ( есть только одно произносимое слово "1" длины 1, начинающееся на "1")  и $F_{2}=2$ (есть только два произносимых слова "10" и "11" длины 2, начинающиеся с "1"). Таким образом, количество всех произносимых слов длины n равно равно $2F_n$ и равно удвоенному n-ому числу  Фибоначчи. Т.е., начиная с $F_1$, последовательность $F_n$ имеет вид 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ..., где каждое следующее число - сумма двух предыдущих.
$F_{10}=89$, $F_9=55$, а значит, искомая разность равна
$2(F_{10}-F_9)=2F_8=2\cdot 34=68.$