$A\subset \mathbb{N}$ and $(A+1)=\{x+1\mid x\in A\}$. how many subsets of $\{1,2,3,\dots, n\}$ exists, such that $A\cup(A+1)=\{1,2,3,\dots, n+1\}$.

Question

Let $A\subset \mathbb{N}$ and $(A+1)=\{x+1\mid x\in A\}$. For every $n$, how many subsets of $\{1,2,3,\dots, n\}$ like $A$ exists, such that $A\cup(A+1)=\{1,2,3,\dots, n+1\}$.

My try:
As we should have $1$ and $n+1$ in the $A\cup(A+1)$, so $A$ should include $1$ and $n$. Another thing I realized is that for every two elements that are next to each other, we should pick at least one. We can't not pick both of them. For example for $n=4$: $A\subseteq\{1,2,3,4\}$. We cannot pick non of $2$ or $3$. These are all cases:

• $\{1,2,4\}$
• $\{1,3,4\}$
• $\{1,2,3,4\}$

I couldn't find a formula to count these subsets. But I thought maybe we can find a recursive formula for it. Any help or hint is immensely valuable to me.

Answer 1

As you stated, $A$ shall include $1$, $n$ and at least one from each pair of consecutive elements in $\{2, \dots, n-1\}$. In fact, that's pretty much all there is to it. Every set $A$ satisfying this will be such that $$A\cup(A+1)=\{1,\dots, n+1\}$$ Let $x_n$ be the amount of such sets.

• If $n-1\in A$, then $A=\{n\}\cup B$, where $B\subset\{1,\dots,n-1\}$ includes $1, n-1$ and at least one from each pair of consecutive elements in $\{2, \dots, n-2\}$. There are $x_{n-1}$ such sets.
• If $n-1\not\in A$, then $n-2\in A$, so $A=\{n\}\cup B$, where $B\subset \{1,\dots,n-2\}$ includes $1, n-2$ and at least one from each pair of consecutive elements in $\{2, \dots, n-3\}$. There are $x_{n-2}$ such sets.

This shows $x_n=x_{n-1}+x_{n-2}$, which is the Fibonacci's recurrence equation. For initial terms we get $x_1=x_2=1$, so these are truly just the Fibonacci numbers.