Задача
COM-B1-M11-P006 Без соседних
#6
★★☆☆☆ Уровень 2 из 5
Сколько подмножеств множества \(\{1,2,\ldots,6\}\) не содержат двух соседних чисел?
Разделите по числу \(6\).
Пусть \(a_n\) - число таких подмножеств для \(\{1,\ldots,n\}\). Тогда \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Получаем \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\).
Рекурсия скрыта в условии про соседей.