6

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.

Asaf Karagila
  • 393,674
Nathaniel Lackey
  • 63
  • I haven't worked it out, but in these situations it's often helpful to think about splitting cases for $n+1$ according to whether $n+1\in S$ or not. You might be able to count the number of $S$'s of each type using the induction hypothesis – Jamie Radcliffe Sep 13 '21 at 12:45
  • 1
    Compare this to the problem of tiling an $n\times 1$ board with dominos ($2\times 1$ pieces) and monominos ($1\times 1$ pieces). The position of the left-side of each piece corresponds to each number in your set $S$. Where a domino occurs implies that the number corresponding to the middle is not present in $S$ (but is present in $S+1$ and so present in $S\cup S+1$). The solution to the number of such tilings is well known to be the Fibonacci sequence, hence your problem is too. – JMoravitz Sep 13 '21 at 12:52
  • 1
    For instance, consider the tiling [.][. .][.][. .] which corresponds to $S={1,2,4,5}$ or the tiling [.][.][.][.][. .][. .] which corresponds to $S={1,2,3,4,5,7}$ on so on. If unsatisfied with just equating the two problems together, then consider looking at the proof used for the tiling problem and just rewording the proof to fit your current case. – JMoravitz Sep 13 '21 at 12:57
  • 2
    Does this answer your question? "Fat" sets of integers and Fibonacci numbers – ə̷̶̸͇̘̜́̍͗̂̄︣͟ Sep 13 '21 at 14:54
  • @TheSimpliFire I think you misread, that is clearly not a duplicate (I mean, I guess all "prove $F_n$ counts this combinatorial object questions" are equivalent, but there is no obvious bijection between $S$ such that $S\cup (S+1)=[n+1]$ and fat subsets). – Mike Earnest Sep 13 '21 at 15:14

1 Answers1

3

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:

  1. $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$.

  2. $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!

Isky Mathews
  • 3,235
  • 11
  • 25
  • 1
    Thank you! It took me a few reads to understand what you did, but once it clicked, it really clicked! Now I feel I have a much better understanding of this problem. Again, thank you! – Nathaniel Lackey Sep 13 '21 at 22:22