# Two elements in the set differ by 3 or more

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.

• Wouldn't we also have to remove $n - 2$ in order to include $n$? Commented Aug 20, 2020 at 20:45
• Either $n$ is in the set, in which case you have $a_{n-3}$ since we know that $n-2, n-1$ can't be in the set, or $n$ is not in the set, in which case you have $a_{n-1}$.
– lulu
Commented Aug 20, 2020 at 20:54
• @FruDe I read the condition as requiring that no two elements are closer than $3$, so I would not count the set you propose.
– lulu
Commented Aug 20, 2020 at 20:56
• @lulu Alright, I'll go with that. So then the recursion would be $a_n = a_{n-1}+a_{n-3}$. Commented Aug 20, 2020 at 20:58
• When mathematicians say something like "any two" they mean "for all pairs." Your interpretation seems closer to saying "for some pair." Commented Aug 20, 2020 at 22:56

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.