Problem
COM-B1-M10-P013 Subsets Without Neighbors
#13
★★★☆☆ Level 3 of 5
Prove that the number of subsets of \(\{1,2,\ldots,n\}\) containing no two consecutive numbers satisfies \(a_n=a_{n-1}+a_{n-2}\).
Split subsets by whether they contain \(n\).
If a subset does not contain \(n\), it is a valid subset of \(\{1,\ldots,n-1\}\), giving \(a_{n-1}\) choices. If it contains \(n\), then it does not contain \(n-1\), and the remaining part is a valid subset of \(\{1,\ldots,n-2\}\), giving \(a_{n-2}\) choices. The cases are disjoint and exhaustive, so \(a_n=a_{n-1}+a_{n-2}\).
The proof of the recurrence is more important than computation.