Counting the number of subsets with a given property Let $S = \{1, 2, 3, \ldots, 12\}$ be a set. How many subsets $S' \subseteq S$ satisfy the property that for any $x, y\in S'$, $|x - y| > 2$?
This is a problem from a math contest, but I'm not so sure how to figure it out. I tried splitting it into casework on the sizes.
For example, I think $|S'| = 4$ is the maximal sized subset but there are even a lot of possible subsets for that size.
For $|S'| = 1$, there are $12$ possible subsets (the condition is vacuously true). 
I'm sure there's probably some really clever way to count these subsets, and I am seeking help to find it.
Thanks
Following lulu's approach (in comments):


*

*$a_1 = 2$ (empty set and the singleton)

*$a_2 = 3$ (two possible singletons and the empty set)

*$a_3 = 4$ (three possible singletons and the empty set)
Now using the recurrence $a_n = a_{n - 1} + a_{n - 3}$, we get $a_4 = 6$, $a_5 = 9$, $a_6 = 13$, $a_7 = 19$, $a_8 = 28$, $a_9 = 41, a_{10} = 60, a_{11} = 88, a_{12} = 129$.
So the answer is $129$. Is this right?
 A: You are correct.
Here is another approach.
Clearly, the condition that $|x - y| > 2$ cannot be violated by the empty set or by a singleton set.  There is one empty set, and there are $12$ singleton sets that are subsets of $S$.
Next, we count admissible subsets with two elements.  We will arrange $8$ blue, $2$ green, and $2$ red balls so that there are two red balls between the pair of green balls. We first line up $8$ blue and $2$ green balls.  To ensure that there are at least two balls between the pair of green balls, we now insert two red balls to the immediate right of the first green ball.  We now number the balls from left to right.  The numbers on the green balls are the desired subset of $S$.  The number of such subsets is the number of ways we can line up the eight blue and two green balls, which is $\binom{10}{2} = 45$.
To count admissible subsets with three elements, we will arrange $5$ blue, $3$ green, and $4$ red balls so that there are two red balls between each pair of green balls.  We first line up the $5$ blue and $3$ green balls.  To ensure that there are at least two balls between each pair of green balls, we insert two red balls to the immediate right of the first and second green balls.  We then number the balls from left to right.  The numbers on the green balls are the desired subset of $S$.  The number of such subsets is the number of ways we can line up the five blue and three green balls, which is $\binom{8}{3} = 56$.
To count admissible subsets with four elements, we arrange $2$ blue, $4$ green, and $6$ red balls so that there at two red balls between each pair of green balls.  We first line up $2$ blue and $4$ green balls.  To ensure that there are at least two balls between each pair of green balls, we insert two red balls to the immediate right of each of the first three green balls.  We then number the balls from left to right.  The numbers on the green balls are the desired subset of $S$.  The number of such subsets is the number of ways we can line up two blue and four green balls, which is $\binom{6}{2} = 15$.
As you observed, it is not possible to have a subset of $S$ with five or more elements, each of which are more than two units apart since then the largest number would have to be at least $1 + 4 \cdot 3 = 13 > 12$.
In total, there are 
$$\binom{12}{0} + \binom{12}{1} + \binom{10}{2} + \binom{8}{3} + \binom{6}{2} =  1 + 12 + 45 + 56 + 15 = 129$$
admissible subsets of $S$.
