Let $a_n$ be the number of subsets of $\{1,2,3,\ldots,n\}$ that do not contain any two consecutive integers. Which of the following statements is/are correct?
Step-by-Step Solution
Key Concept: The recurrence $a_n=a_{n-1}+a_{n-2}$ holds: either $n\notin$ subset (giving $a_{n-1}$ subsets of $\{1,\ldots,n-1\}$) or $n\in$ subset (then $n-1\notin$ subset, giving $a_{n-2}$ subsets of $\{1,\ldots,n-2\}$). Initial: $a_1=2$ ($\emptyset,\{1\}$), $a_2=3$ ($\emptyset,\{1\},\{2\}$).
$a_1=2,a_2=3,a_3=5,a_4=8,a_5=13,a_6=21$. A ✓ (recurrence), B ✓ ($a_5=13$), C ✓ ($a_6=21$), D ✗ ($a_4=8\neq 7$). Answer: A, B, C.
Correct Answer: ABC