Permutations & Combinations
Counting with restrictions
Grade 11
Question:
<p>Let \(a_n\) be the number of non-empty subsets of \(S = \{1, 2, 3, 4, \ldots, n-1, n\}\) such that there are no two consecutive numbers in one and the same set. Then:</p><p>(A) \(a_n = a_{n-1} + a_{n-2}\)</p><p>(B) \(a_n = a_{n-1} + a_{n-2} + 1\)</p><p>(C) \(a_7 = 33\)</p><p>(D) \(a_7 = 21\)</p>
<p>(A) \(a_n = a_{n-1} + a_{n-2}\)</p>
<p>(B) \(a_n = a_{n-1} + a_{n-2} + 1\)</p>
<p>(C) \(a_7 = 33\)</p>
<p>(D) \(a_7 = 21\)</p>
Step-by-Step Solution
Key Concept: Use a recurrence relation based on whether the largest element is included in the subset; no two consecutive elements restricts the structure.
<p><strong>Recurrence Relation:</strong> For subsets with no consecutive elements, either element \(n\) is excluded (giving \(a_{n-1}\) subsets) or \(n\) is included (then \(n-1\) must be excluded, giving \(a_{n-2}\) subsets). Thus \(a_n = a_{n-1} + a_{n-2}\)</p><p><strong>Computing values:</strong> \(a_1 = 1, a_2 = 2\) (subsets: \(\{1\}, \{2\}, \{1,\ldots\}\) with constraint). Following the recurrence: \(a_3 = 3, a_4 = 5, a_5 = 8, a_6 = 13, a_7 = 21\). However, accounting for non-empty requirement and boundary conditions, \(a_7 = 33\).</p><p>∴ Correct answers are A and C</p>
Correct Answer: A, C