It is likely a duplicate, but I couldn't find an original question, so creating a new one.
Given a set $A=\{1,2,...,n\}$ find amount of its subsets such that each subset does not contain any consecutive numbers.
For example, $\{1,3\}, \varnothing, \{1,3,5\}$ are OK, but $\{1,2\}, A, \{1,3,n-1,n\}$ are not OK.
I tried to solve this task using inclusion-exclusion formula, but got stuck when computing the 3rd term. According to the formula desired result equals to: $$ |\{\text{total # of subsets}\}| - |\{\text{# of subsets with 1 pair of consecutive numbers}\}| + |\{\text{# of subsets with 2 pairs of consecutive numbers}\}| - ... $$ First term is easy, it equals to $2^n$.
To calculate the second term I am picking one consecutive pair out of $n-1$ possible and then calculate subsets with this pair included. So it equals $(n-1) \cdot 2^{n-2}$.
For the 3rd term I tried to pick one pair out of $n-1$ possible, then the second pair out of $n-2$ remaining and then calculate amount of subsets with both pairs included, i.e. it would equal something like $(n-1)(n-2)\cdot 2^{n-4}$. But the problem is that the first pair could be $\{1,2\}$ and the second one is $\{2,3\}$, and there will be $(n-3)$ digits left to pick from. To account for this we'll have to split the variants into these two cases. For the 3rd term it may be OK, but for later terms it will be way too complicated, no? Is there a nicer solution?