Problem
COM-B1-M11-P006 No Consecutive
#6
★★☆☆☆ Level 2 of 5
How many subsets of \(\{1,2,\ldots,6\}\) contain no two consecutive numbers?
Split by the number \(6\).
Let \(a_n\) be the number of such subsets of \(\{1,\ldots,n\}\). Then \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Thus \(a_2=3\), \(a_3=5\), \(a_4=8\), \(a_5=13\), \(a_6=21\).
The recurrence is hidden in the adjacency condition.