Задача
COM-B1-M10-P013 Подмножества без соседей
#13
★★★☆☆ Уровень 3 из 5
Докажите, что число подмножеств множества \(\{1,2,\ldots,n\}\), не содержащих двух соседних чисел, удовлетворяет рекурсии \(a_n=a_{n-1}+a_{n-2}\).
Разделите подмножества на те, которые содержат \(n\), и те, которые не содержат.
Если подмножество не содержит \(n\), оно является допустимым подмножеством \(\{1,\ldots,n-1\}\), таких \(a_{n-1}\). Если содержит \(n\), то не содержит \(n-1\), а оставшаяся часть является допустимым подмножеством \(\{1,\ldots,n-2\}\), таких \(a_{n-2}\). Эти случаи не пересекаются и покрывают все варианты, поэтому \(a_n=a_{n-1}+a_{n-2}\).
Доказательство рекурсии важнее вычисления.