We say that a set of integers is sparse if any two distinct elements in the set differ by at least 3. Find the number of sparse subsets of {1, 2, 3, ... , 12}. (Note that the empty set is also sparse.)
+1262 The sparse subsets of {1} are {} and {1}, so there are 2 subsets of {1}.
The sparse subsets of {1,2} are {}, {1}, and {2}, so there are 3 subsets of {1,2}.
The sparse subsets of {1,2,3} are {}, {1}, {2}, and {3}, so there are 4 subsets of {1,2,3}.
The sparse subsets of {1,2,3,4} are {}, {1}, {2}, {3}, {4}, and {1,4} so there are 6 subsets of {1,2,3,4}.
The sparse subsets of {1,2,3,4,5} are {}, {1}, {2}, {3}, {4}, {5}, {1,4}, {1,5} and {2,5} so there are 9 subsets of {1,2,3,4,5}.
We found a pattern! The number of sparse subsets of {1,2,3, ... ,n} is the number of subsets of {1,2,3, ... ,n-1}+{1,2,3, ... ,n-3}. So the number of subsets of {1,2,3, ... ,12} is \(\boxed{\text129}\).
