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 ?

An $n$-word is just a binary string of length $n$. Given an $n$-word, you can construct a subset of $\{1,2,\ldots,n\}$ by including $i$ if and only if the $i$th digit of the $n$-word is a $1$, and vice versa. This is the bijection. In the problem at hand, a subset has no consecutive numbers if and only if its corresponding $n$-word has no adjacent $1$'s.

An $n$-word is a word of length $n$. Call a set with no consecutives good.

There are two types of good set (i) the ones that do not contain $1$, and (ii) the ones that contain $1$.

There are $a_{n-1}$ good subsets of $\{1,2,\dots,n\}$ of Type $1$. There are $a_{n-2}$ good subsets of $\{1,2,\dots,n\}$ of Type (ii), since if our set contains $1$, then $2$ is forbidden.

Remark: The author has chosen to phrase things in terms of characteristic functions instead of subsets. That makes no difference, characteristic functions and subsets are essentially the same.

A $n$-word is a word with $n$ letters, 00, 01, 10, 11 are the $2$-words on the alphabet $\{0,1\}$.

Proposition. Let $E$ be a set, then the subsets of $E$ are in bijection with $\{0,1\}^E$.

Proof. Let define the following map: $$\varphi:\left\{\begin{array}{ccc}\mathcal{P}(E)&\to&\{0,1\}^E\\A&\mapsto&x\in E\mapsto\left\{\begin{array}{ll}0&\textrm{, if }x\notin A\\1&\textrm{, if }x\in A\end{array}\right.\end{array}\right..$$ $\varphi$ is a bijection whose inverse is given by: $$\left\{\begin{array}{ccc}\{0,1\}^E&\to&\mathcal{P}(E)\\f&\mapsto&\{x\in E\textrm{ s.t. }f(x)=1\}\end{array}\right..$$ Whence the result. $\Box$

In your case, your proposition tells us that the subsets of $\{1,\cdots,n\}$ are in bijection with $\{0,1\}^{\{1,\cdots,n\}}$, that is the $n$-words on the alphabet $\{0,1\}$.

Can you see from there why the number of $n$-words without consecutive $1$s is the number of subsets of $\{1,\cdots,n\}$ without consecutive numbers?