How many subsets does the set {1,2,3,...n} have that contain no three consecutive integers? Find a recurrence

Question

Q: How many subsets does the set $\{1,2,3,...n\}$ have that contain no three consecutive integers? Find a recurrence.

I don’t think I understand the solution.

According to the solution if I take out $n-1$ from $\{1,2,3,\ldots , n-1, n\}$, then I would have $S_{n-2}$ to the left of $n-1$, which I get, but then I have ‘$n$’ which I don’t know what to do with. For every subset associated with $S_{n-2}$, there’s now an element ‘$n$’ available to either include or not include in the subset, which increases the size of $S_{n-2}$. If pretend ‘$n$’ isn’t there it would give us $S_{n-2}$ exactly.

The same goes for $S_{n-2}$ and $S_{n-3}$. The $S_n$ would then be a lower bound.

What am I not getting about this question?  

Answer 1

Let $A \subseteq \{1, 2, \cdots, n \}$ satisfies the condition. We can divide to three cases:

• $n \not \in A$: Then, there are $S_{n-1}$ possibilities for $A$
• $n \in A$:
  • $n-1 \not \in A$ : Then, there are $S_{n-2}$ possibilities of $A$ since $A - \{n\}$ is three-consecutive-integer-free and belongs to $\{1, 2, \cdots, n-2\}$.
  • $n-1 \in A$: Then, $n-2 \not \in A$. Now we have $A - \{n-1, n \} \subset \{1, 2, \cdots, n-3\}$, so there are $S_{n-3}$ possibilities for $A$.

Therefore, $S_n = S_{n-1} + S_{n-2} + S_{n-3}$.