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

Пусть — это количество слов инопланетят, состоящих из букв.

Заметим, что единственное однобуквенное слово — это слово А. Двухбуквенных слов вообще нет, так как первая и последняя, то есть первая и вторая буквы — это А, но тогда две буквы А стоят рядом, что противоречит определению инопланетного слова. Трёхбуквенное слово тоже только одно — АБА. И четырёхбуквенное слово единственно — АББА. Таким образом,

Рассмотрим теперь какое-нибудь слово длины где Его последняя буква — это точно буква А, так как каждое слово начинается и заканчивается буквой А. Предпоследняя буква — это Б, так как две буквы А не могут идти подряд. Есть два варианта, какой может быть буква перед Б, то есть предпредпоследняя буква слова :

1) Это буква А. Тогда слово имеет вид А...АБА. Рассмотрим строку из первых букв этого слова. Она начинается и заканчивается на А, а так же в ней нет двух букв А подряд или трёх букв Б подряд, так как иначе не было бы словом. А значит эта строка сама является словом.

2) Это буква Б. Тогда перед этой буквой Б стоит буква А, там как три буквы Б не могут идти подряд, и слово имеет вид А...АББА. Аналогично случаю 1, строка, образованная первыми буквами будет являться словом.

Получается, что слово могло быть получено либо приписыванием строки БА в конец какого-нибудь слова из букв, либо приписыванием строки ББА в конец какого-нибудь слова из букв. При этом, приписав в конец каждого из слов длины строку БА, мы получим различных слов длины Аналогично, приписав в конец каждого из слов длины строку ББА, мы получим различных слов длины Отсюда,

Пользуясь этой формулой, найдем для

Итак, в словаре сказочной планеты 86 20-буквенных слов.