How many subsets of $\{1,2,...,n\}$ do not contain three consecutive integers?

Partial solution: Let's denote by $S \subseteq \{1,2,\dots,n\}$ all sets that satisfy the condition. And let $a_n$ be the number of such sets.

There may be some cases:

1. $n \not \in S \implies$ there are $a_{n-1}$ possibilities for $S$ (clear)
2. $n \in S$:

• a) $n-1 \not \in S \implies$ there are $a_{n-2}$ possibilities for $S$ (why?)
• b) $n-1 \in S, \ \ n-2 \not \in S \implies$ there are $a_{n-3}$ possibilities for $S$. (why?)

Hence, we get the recurrence formula $$\boxed{a_n = a_{n-1} + a_{n-2} + a_{n-3}}$$

---

Answer two (why?) parts above and it will become a full solution.

Sketch for the solution: you can construct a recursion to find this number. Let $x_k$ the number of subsets in $\{1,\ldots ,k\}$ that doesn't contain three consecutive numbers, then $x_{k+1}=x_k+x_{k-1}+x_{k-2}$ because

• $x_k$ is the number of subsets in $\{1,\ldots ,k+1\}$ that doesn't contain $k+1$ and dont have three consecutive numbers
• $x_{k-1}$ is the number of subsets in $\{1,\ldots ,k+1\}$ that contains $k+1$ but doesn't contain $k$ and doesn't contain three consecutive numbers
• $x_{k-2}$ stay for the subsets in $\{1,\ldots ,k+1\}$ that contains $k+1$ and $k$ but doesn't contains three consecutive numbers.

Here's perhaps another approach. (Well it's basically equivalent to the answers already given, but maybe the binary string representation makes the problem easier to think about. At least it does for me, but that might be because I happened to already be familiar with these "run length problems".)

You can think a subset $S$ of $\{1,\dots, n\}$ as a binary string of length $n$, where $1$ at position $j$ means $j\in S$ and $0$ means $j\notin S$. Now, the subsets we want to count correspond to binary strings without a $3$-run of $1$'s.

To solve this new problem, lets denote

$$A_n = \{\text{length } n \text{ binary strings without a run of three 1's} \}$$

Now think of a $w\in A_n$ and the number of $1$'s it has in the beginning. That can be either $0$, $1$ or $2$. Then there is a zero and the rest is a word in $A_{n-1}$, $A_{n-2}$ or $A_{n-3}$, respectively. We're assuming $n>3$; the first ones are base cases. You can see the tribonacci-recursion for the size $|A_n|$.