Пусть

-- количество способов, которыми можно последовательность из

знаков разбить на одно- и двухзнаковые буквы.
Рассмотрим последовательность из

знаков. Последний знак входит либо в однознаковую букву, либо в двухзнаковую.
Если последний знак входит в однознаковую букву, то часть последовательности без последней буквы содержит

знаков и может быть разбита на буквы

способами.
Если последний знак входит в двухзнаковую букву, то часть последовательности без последней буквы содержит

знаков и может быть разбита на буквы

способами.
В каждом из этих способов мы имеем вполне определенное разбиение (знаем, как отделить последнюю букву, и знаем, как разбить предыдущую часть последовательности).
Итого

способов, что совпадает с рекуррентной формулой для чисел Фибоначчи. Считайте, что это шаг индукции, а базу Вы легко докажете сами.