Set question which I believe relates to Fibonacci numbers. For a subset $S$ of $\mathbb{N}$, let us define $S+1=\{x+1: x \in S\}$. How many subsets $S$ of the set $\{1,2,...,n\}$ satisfy the condition $S\cup \left(S+1\right)=\{1,2,...,n+1\}$?
I think that the amount of subsets is the $nth$ Fibonacci number. I looked at the cases for $n=1,2,3,4,5$ and I find $1,1,2,3,5$ subsets respectively. My professor suggested a proof by induction, but I don't see how to invoke the inductive hypothesis here.
Examining $n=3$. We want to show the subsets which give $S\cup \left( S+1\right)=\{1,2,3,4\}$.
Subsets $S$ include: $\{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1, 2, 3\}$.
Subsets $\left( S+1\right)$ include: $\{2\}, \{3\}, \{4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{2, 3, 4\}$. So, the only cases in which  $S\cup \left( S+1\right)=\{1,2,3,4\}$ is when $S=\{1, 3\}$ and $S=\{1, 2, 3\}$. In other words, we have two subsets which satisfy the relationship when $n=3$.
As mentioned, I did this for $n=1,2,3,4,5$ to find a pattern, and it appears to be the Fibonacci sequence, but again, I am completely unsure how to show this through induction. Any help would be appreciated.
 A: I have below what I believe to be a direct bijective proof by induction. Let us refer to the number of possible such subsets $S$ as $S_n$. You have already manually shown that $S_n = F_n$ for $n=1,2,3,4,5$ so we now show that $S_{n+1} = S_n+S_{n-1}$.
Consider any $S\subseteq \{1,...,n+1\}$ so that $S\cup (S+1) = \{1,..., n+2\}$. Clearly $n+2\in (S+1)$ but $n+2\notin S$ and so we know that $n+1\in S$. Now there are two possibilities:

*

*$n\in S$. If this is the case, then observe that $S' =  S\setminus \{n+1\}$ has the property that $S'\subseteq \{1,...n\}$ and also that $S'\cup (S'+1) = \{1,..., n+1\}$. Similarly observe that for any set $U$ that satisfies these requirements (i.e. are one of those counted by $S_n$) we may take $U' = S\cup\{n+1\}$ and see that $U'\subseteq \{1,...n+1\}, U'\cup (U'+1) = \{1,..., n+2\}$. Thus there are precisely $S_n$ sets $S$ in this case where $n\in S$.


*$n\notin S$. If this is the case, we know that $S' =  S\setminus \{n+1\}$ has the property that $S'\subseteq \{1,...n-1\}$ and also that $S'\cup (S'+1) = \{1,..., n\}$. Similarly observe that every set $U$ counted by $S_{n-1}$ can have $n+1$ appended to it to get a set $U'$ such that $U'\subseteq \{1,...n+1\},U'\cup (U'+1) = \{1,..., n+1\}$. Thus there are precisely $S_{n-1}$ sets $S$ in this case where $n\notin S$.
Given it is either true that $n\in S$ or that $n\notin S$, we see that $S_{n+1} = S_n+S_{n-1}$, showing the result by induction!
