Или сначала мы должны попытаться их вывести?
Там ничего сложного. Пусть

это множество всех последовательностей длины

,

это множество последовательностей из нулей и единиц длины

, в которой

единиц идут подряд. Множество

(

) легко получить как объединений двух множеств

и

. Во-первых, мы может ко всем элементам множества

приписать либо нуль, либо единицу, получив тем самым множество

. Во-вторых, мы можем к тем элементам из

, которые заканчиваются на нуль и

единиц приписать единицу, получив множество

. Получим

. Или

.
Далее, сразу получаем

. Также

(первые

элементов последовательности мы вправе выбирать по желанию, далее идет нуль,

единиц). В качестве упражнения посчитайте

и получите рекуррентную формулу, по которой можно считать

за

операций:
