Subsets without two consecutive integers

1. Recurrence. Take $n\ge2$ and split the admissible subsets of $\{1,\dots,n\}$ into two classes.
- Those not containing $n$: they are exactly the admissible subsets of $\{1,\dots,n-1\}$, so there are $a_{n-1}$.
- Those containing $n$: they do not contain $n-1$, and removing $n$ leaves an admissible subset of $\{1,\dots,n-2\}$; conversely adding $n$ to such a subset is admissible. So there are $a_{n-2}$.

Hence $a_n=a_{n-1}+a_{n-2}$. The initial values are $a_0=1$ and $a_1=2$, which are $F_2$ and $F_3$. By induction $a_n=F_{n+2}$.

2. Bijection. Let $x_1<x_2<\dots<x_k$ be an admissible subset, so $x_{i+1}\ge x_i+2$. Define $y_i=x_i-(i-1)$. Then $y_{i+1}-y_i\ge1$, so $y_1<\dots<y_k$, and $1\le y_1$, $y_k\le n-k+1$. Conversely, from any $k$-subset $y_1<\dots<y_k$ of $\{1,\dots,n-k+1\}$, setting $x_i=y_i+(i-1)$ gives an admissible subset. These maps are inverse, so the count is $\binom{n-k+1}k$.

Check. Summing over $k$ gives $\sum_k\binom{n-k+1}k=F_{n+2}$.

Lesson. Recurrence by conditioning on the last element, and bijections that "squeeze out" a constraint.