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 ?
Best Answer
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.