How many subsets of {1, 2, 3, 4..... 12} can be formed such that no two…
2025
How many subsets of {1, 2, 3, 4..... 12} can be formed such that no two elements in the subset are consecutive?
- A.
144
- B.
377
- C.
610
- D.
89
Attempted by 150 students.
Show answer & explanation
Correct answer: B
Approach: Let A(n) be the number of subsets of {1, 2, ..., n} in which no two selected elements are consecutive.
Do not include n: then the subset can be any valid subset of {1, 2, ..., n − 1}, giving A(n − 1) choices.
Include n: then n − 1 cannot be included, so the remaining elements come from {1, 2, ..., n − 2}, giving A(n − 2) choices.
Therefore, A(n) = A(n − 1) + A(n − 2). This is the Fibonacci recurrence.
Base cases: A(0) = 1 for the empty set, and A(1) = 2 for {} and {1}.
Values up to n = 12: A(2)=3, A(3)=5, A(4)=8, A(5)=13, A(6)=21, A(7)=34, A(8)=55, A(9)=89, A(10)=144, A(11)=233, A(12)=377.
Answer: 377