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