Рекурренты в комбинаторике и числа Фибоначчи f(n)

Обозначим через количество слов длины , состоящих только из букв “а” и “б” и не содержащих в записи двух букв “б” подряд. Таким образом, находим , . Покажем, что можно выразить через и . Количество слов длины , не содержащих в записи двух букв “б” подряд и начинающихся с буквы “а”, равно , так как после первой буквы может следовать любое слово длины , не содержащее двух “б” подряд. Пусть слово длины начинается с буквы “б”. Если в этом слове нет двух “б” подряд, то вторая буква — “а”, а далее может следовать любое слово длины , не содержащее двух “б” подряд. Таким образом, количество слов длины , не содержащих в записи двух букв “б” подряд и начинающихся с буквы “б”, равно . Тем самым, мы показали, что . Теперь последовательно вычисляем , и так далее, .