How many subsets contain no consecutive elements? How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers ?
Here is the solution :
The subsets are interpreted as $n$-words from the alphabet $\{0,1\}$. Let $a_n$ be the number of words with no consecutive ones. Then, a word can start from $0$ and proceed in $a_{n-1}$ ways or start with $10$ and proceed in $a_{n-2}$ ways. Therefore, $a_{n} = a_{n-1} + a_{n-2}$. $a_1 = 2, a_2 = 3$. So, $a_n = F_{n+2}$.
I have no trouble understanding the part of the argument linking $a_n$ with the Fibonacci numbers. But, I have trouble understanding the bijective argument.
What is a $n$ word ? And, how is the bijective constructed here ? How is $a_n$ linked to the question ?

Choose the first value in the set:
$$\sum_{q=1}^n z^q = z \sum_{q=0}^{n-1} z^q = z\frac{1-z^n}{1-z}.$$
Choose some number of gaps that are at least two:
$$\sum_{p=0}^{n-1} \left(\frac{z^2}{1-z}\right)^p
= \frac{1-z^{2n}/(1-z)^n}{1-z^2/(1-z)}.$$
Sum  the  contributions  that end  in  at  most  $n$ and  extract  the
coefficient:
$$[z^n] \frac{1}{1-z} z\frac{1-z^n}{1-z}
\frac{1-z^{2n}/(1-z)^n}{1-z^2/(1-z)}
\\ = [z^{n-1}] \frac{1-z^n}{1-z}
\frac{1-z^{2n}/(1-z)^n}{1-z-z^2}.$$
Eliminate the terms that do not contribute to $[z^{n-1}],$ first
$$[z^{n-1}] \frac{1-z^n}{1-z}
\frac{1}{1-z-z^2}.$$
and second
$$[z^{n-1}] \frac{1}{1-z} \frac{1}{1-z-z^2}
= [z^{n-1}]
\left(\frac{2+z}{1-z-z^2}-\frac{1}{1-z}\right).$$
Extracting coefficients we obtain
$$F_{n-1} + 2 F_n - 1
= F_n + F_{n+1} - 1 = F_{n+2} - 1.$$
Remark. Here we have not counted the empty set as pointed out in the comments. The answer is $$F_{n+2}$$ if the empty set is included, which it should be.
