TITLE: Two elements in the set differ by 3 or more
QUESTION [3 upvotes]: Call a set of integers sparse if any two elements in the set differ by at least 3. Find the number of sparse subsets of $\{1, 2, 3, \dots, 12\}.$ (Both $\emptyset$ and one-element sets are sparse, to my understanding.) For example, {$1, 5, 11, 12$} is a sparse set, since $1$ and $5$ differ by 3 or more.

I was thinking of a way using recursion. Here's my approach:
Call $a_n$ the number of sparse sets in the set of integers {$1, 2, 3, \dots, n$}.  If we look at the set {$1, 2, 3, \dots, n-1$}, there are $a_{n-1}$ sparse sets. If we assign $n-1$ to a sparse set, when we incorporate $n$, then we can either

include $n$ in the sparse set
include $n$ and remove $n-1$ in the sparse set
keep it as it is.

There are $3$ cases, each with the same value, so we have $a_n = 3a_{n-1}$ so far.
However, I don't know how to continue, and I'm not even sure if my current approach is correct.

REPLY [1 votes]: Let $S_n$ be the set of sparse subsets on $\{1..n\}$. Then $S_0 = \{\emptyset\}$, $S_1 = \{\emptyset, \{1\}\}$, $S_2 = \{\emptyset, \{1\}, \{2\}\}$, and in general
$S_{n + 3} = S_{n + 2} \cup \{A \cup \{n + 3\} : A \in S_n\}$
Define $F_n = |S_n|$. Then we see that $F_0 = 1$, $F_1 = 2$, $F_2 = 3$, and $F_{n + 3} = F_{n + 2} + F_n$.
To efficiently calculate $F_n$, we note that, defining
$M = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$
We have
$M \begin{pmatrix} F_{n + 2} \\ F_{n + 1} \\ F_n \end{pmatrix} = \begin{pmatrix} F_{n + 3} \\ F_{n + 2} \\ F_{n + 1} \end{pmatrix}$
And consequently, by induction on $n$, we have
$M^n \begin{pmatrix} F_{2} \\ F_{1} \\ F_0 \end{pmatrix} = \begin{pmatrix} F_{n + 2} \\ F_{n + 1} \\ F_{n} \end{pmatrix}$
Calculating $M^n$ will take $O(\log n)$ multiplications.
{"set_name": "stack_exchange", "score": 3, "question_id": 3797959}