Computing the Number of Ordered Subsets of $\{1,...,n\}$ that Contain no Consecutive Elements Question: Let $f(n)$ be the number of subsets of $[n]=\{1,...,n\}$ that contain no two consecutive elements, for integer $n$. Find the recurrence that is satisfied by these
numbers, and then ‘find’ the numbers themselves.
Book Answer: Among these subsets we distinguish those that do contain $n$ and those that don’t. If such a subset contains $n$, then the rest of that subset is one of the subsets that is counted by $f(n − 2)$. If it does not contain $n$ then the entire subset is one of those that is counted by $f(n − 1)$. Thus $f(n) = f(n−1)+f(n−2)$, which together with the starting values $f(1) = 2$, $f(2) = 3$ tells us that $f(n) = F_{n+2}$, where the $F$’s are the Fibonacci numbers.
Question:  I feel comfortable with the fact that if a set $S$ contains $n$, $S\setminus n \subset \{1,...,n-2\}$ as $n-1$ is consecutive to $n$ and must also be removed when $n$ is present. I do not understand the terminology that $S \setminus n$ will be counted by $f(n-2)$.
I initially wondered how the placement of $n$ would modify the counting process of $f(n-2)$. Then, I remembered that the problem asked for count unordered sets as opposed to ordered lists. Now, I wonder how the question would change if the order of the elements was important.
 A: An example with a specific $n$ is illustrative.
Suppose $n = 7$.  Then an ordered non-consecutive subset of $\{1, 2, 3, 4, 5, 6, 7\}$ that contains $7$ might be
$$(1, 4, 7).$$
Notice that the fact that the last element is $7$ means that $6$ is excluded from the possible choices for the other elements, and that one must choose among the set $\{1, 2, 3, 4, 5\}$ for the other elements; in this case, $(1, 4)$ was chosen.  Consequently, the number of ordered non-consecutive subsets of $\{1, 2, 3, 4, 5, 6, 7\}$ that contain $7$ is equal to the number of ordered non-consecutive subsets of $\{1, 2, 3, 4, 5\}$.
On the other hand, if an ordered non-consecutive subset of $\{1, 2, 3, 4, 5, 6, 7\}$ does not contain $7$, then obviously its elements are chosen among $\{1, 2, 3, 4, 5, 6\}$.
Thus the total number of non-consecutive subsets of $\{1, 2, 3, 4, 5, 6, 7\}$ is equal to the sum of the number of non-consecutive subsets of $\{1, 2, 3, 4, 5\}$ and of $\{1, 2, 3, 4, 5, 6\}$.
As there was nothing special about our choice $n = 7$, we see how the argument generalizes to any $n \ge 3$.
However, we must also take care to define what happens when $n \le 2$.  In the $n = 2$ case, we can count $(1)$ or $(2)$, so there are at least two non-consecutive subsets of $\{1, 2\}$ in the sense that there lacks two elements whose difference is $1$.  But should we count the empty set?  Does it make sense to say the empty set contains no consecutive elements?  The book's answer seems to suggest so by simply claiming $f(2) = 3$.
