Problem
COM-B1-M10-P012 No Consecutive Numbers
#12
★★☆☆☆ Level 2 of 5
How many subsets of \(\{1,2,\ldots,7\}\) contain no two consecutive numbers?
Split by whether \(7\) is included.
Let \(a_n\) be the number of such subsets of \(\{1,\ldots,n\}\). If \(n\) is not included, there are \(a_{n-1}\) ways. If \(n\) is included, then \(n-1\) is not included, leaving \(a_{n-2}\) ways. Hence \(a_n=a_{n-1}+a_{n-2}\), \(a_0=1\), \(a_1=2\). Thus \(a_7=34\).
Connects strings and subsets.