# Combinatorial problems in finding the number of subsets of $S_n$

For $$A \subset \mathbb{R}$$, let $$A'=\{a+1|a \in A\}$$. Let $$S_n=\{1;2;3;...;n\}$$. How many subsets $$A$$ of $$S_n$$ satisfying $$A \cup A' = S_n$$?

I'm trying to solve this problem by using bijection or constructing a sequence but still struggling. Please help me with this.

• Have you tried making examples for small $n?$ – saulspatz Dec 8 '18 at 15:45
• Hint: You can find a recurrence for your answer by conditioning on whether or not $n\in A$. – Mike Earnest Dec 8 '18 at 17:47
• – Anubhab Ghosal Dec 8 '18 at 18:23