Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many [subsets](https://artofproblemsolving.com/wiki/index.php/Subset) of $\{1,2,3,\ldots,12\},$ including the [empty set](https://artofproblemsolving.com/wiki/index.php/Empty_set), are spacy?
$\mathrm{(A)}\ 121 \qquad \mathrm{(B)}\ 123 \qquad \mathrm{(C)}\ 125 \qquad \mathrm{(D)}\ 127 \qquad \mathrm{(E)}\ 129$
Let $S_{n}$ denote the number of spacy subsets of $\{ 1, 2, ... n \}$.  We have $S_{0} = 1, S_{1} = 2, S_{2} = 3$.  
The spacy subsets of $S_{n + 1}$ can be divided into two groups:

$A =$ those not containing $n + 1$.  Clearly $|A|=S_{n}$.
$B =$ those containing $n + 1$. We have $|B|=S_{n - 2}$, since removing $n + 1$ from any set in $B$ produces a spacy set with all elements at most equal to $n - 2,$ and each such spacy set can be constructed from exactly one spacy set in $B$.
Hence,

$S_{n + 1} = S_{n} + S_{n - 2}$
From this [recursion](https://artofproblemsolving.com/wiki/index.php/Recursion), we find that



$S(0)$
$S(1)$
$S(2)$
$S(3)$
$S(4)$
$S(5)$
$S(6)$
$S(7)$
$S(8)$
$S(9)$
$S(10)$
$S(11)$
$S(12)$





1
2
3
4
6
9
13
19
28
41
60
88
129

And so the answer is $\boxed{\textbf{(E)}129}$.