20. How many subsets of the set $\{1,2,3, \ldots, 9\}$ do not contain consecutive odd integers?
20. 208
Solution. Let $a_{n}$ be the number of subsets of $\{1,2, \ldots, n\}$ that do not contain consecutive odd integers. We work on the following cases depending on whether such a subset contains 1 or not:
- If such a subset does not contain 1 , then its elements must consist of elements from $\{2,3, \ldots, n\}$. The number of subsets with no element smaller than 3 is $a_{n-2}$; for each of these subsets, we include 2 as well, giving another $a_{n-2}$ subsets. Thus, there are $2 a_{n-2}$ subsets in this case.
- If such a subset contains 1 , then it must not contain 3 and its elements must consist of elements from $\{1,2,4,5, \ldots, n\}$. The number of subsets with no element smaller than 5 is $a_{n-4}$; for each of these subsets, we take the union with a non-empty subset of $\{2,4\}$ as well, giving another $3 a_{n-4}$ subsets. Thus, there are $4 a_{n-4}$ subsets in this case.
We now obtain the recurrence formula $a_{n}=2 a_{n-2}+4 a_{n-4}$. With $a_{1}=2, a_{2}=4, a_{3}=6$ and $a_{4}=12$, routine computation gives $a_{9}=208$.