Topic: Discrete Mathematics
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
Answer: B. 377
Explanation: The number of subsets of the set $\{1, 2, \dots, n\}$ with no two consecutive elements follows the Fibonacci sequence. Let $S_n$ be the number of such subsets.
For $n=1$, subsets are $\\{\\}$ and $\\{1\\}$ $\implies S_1 = 2 = F_3$.
For $n=2$, subsets are $\\{\\}$, $\\{1\\}$, $\\{2\\}$ $\implies S_2 = 3 = F_4$.
In general, $S_n = F_{n+2}$, where $F_k$ is the $k^{th}$ Fibonacci number ($F_1=1, F_2=1, F_3=2, F_4=3, \dots$).
For $n=12$, we need $F_{14}$.
The sequence proceeds: $F_5=5, F_6=8, F_7=13, F_8=21, F_9=34, F_{10}=55, F_{11}=89, F_{12}=144, F_{13}=233, F_{14}=377$.
Thus, there are 377 such subsets.