Why does the number of subsets with no consecutive integers follow a Fibonacci-like pattern?

The number of subsets of the set $\{1,2,\dots ,n\}$ that contain no two consecutive integers follows a Fibonacci-like pattern because of how these subsets are constructed. Let $f_n$ represent the number of such subsets for a set of size $n$.

Any valid subset of $\{1,2,\dots ,n\}$ falls into one of two mutually exclusive categories:

• Subsets that do not contain $n$: These are simply valid subsets of $\{1,2,\dots ,n-1\}$, of which there are $f_{n-1}$.
• Subsets that do contain $n$: If a subset contains $n$, it cannot contain $n-1$ due to the non-consecutive constraint. Therefore, the remaining elements must form a valid subset of $\{1,2,\dots ,n-2\}$, of which there are $f_{n-2}$.

By summing these two cases, we arrive at the recurrence relation:
$$f_n=f_{n-1}+f_{n-2}$$

With initial values $f_0=1$ (the null set) and $f_1=2$ (the null set and $\{1\}$), this relation generates the sequence 1, 2, 3, 5, 8, and so on, mirroring the structure of the Fibonacci sequence.1