How many subsets of $A=\{0,1,2,...,n\}$ are there such that no consecutive numbers come together

Question

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?

Answer 1

Let $A_n = \{1,2,3,\dots,n\}$. Let $G_n$ be the number of "good" subsets of $A_n$. Here I will consider the empty set to be a "good" subset of each $A_n$.

For each subset, $S$ of $A_n$ there is a function $f_{n,S}:A_n \to \{0,1\}$ define by $f_{n,S}(x)= \begin{cases} 0 & \text{If $x \not \in S$} \\ 1 & \text{If $x \in S$} \\ \end{cases}$

---

\begin{array}{c} & f \\ \text{subset} & 1 & \text{good?} \\ \hline & 0 &\checkmark \\ 1 & 1 &\checkmark \\ \hline \end{array}

So $A_1=2$.

---

\begin{array}{c} & f \\ \text{subset} & 12 & \text{good?} \\ \hline & 00 &\checkmark \\ 1 & 10 &\checkmark \\ 2 & 01 &\checkmark \\ 12 & 11 \\ \hline \end{array}

So $A_2=3$.

---

\begin{array}{c} & f \\ \text{subset} & 123 & \text{good?} \\ \hline & 000 &\checkmark &\text{Compare to $A_2$}\\ 1 & 100 &\checkmark \\ 2 & 010 &\checkmark \\ 12 & 110 \\ \hline 3 & 001 &\checkmark &\text{Compare to $A_1$}\\ 13 & 101 &\checkmark \\ 23 & 011 & \\ 123 & 111 \\ \hline \end{array}

So $A_3=A_1+A_2=5$.

---

\begin{array}{c} & f \\ \text{subset} & 1234 & \text{good?} \\ \hline & 0000 &\checkmark &\text{Compare to $A_3$}\\ 1 & 1000 &\checkmark \\ 2 & 0100 &\checkmark \\ 12 & 1100 \\ 3 & 0010 &\checkmark \\ 13 & 1010 &\checkmark \\ 23 & 0110 & \\ 123 & 1110 \\ \hline 4 & 0001 &\checkmark &\text{Compare to $A_2$}\\ 14 & 1001 &\checkmark \\ 24 & 0101 &\checkmark \\ 124 & 1101 \\ 34 & 0011 & \\ 134 & 1011 & \\ 234 & 0111 & \\ 1234 & 1111 \\ \hline \end{array}

So $A_4=A_2+A_3=8$.

---

So it seems that $A_1=2, \quad A_2=3, \quad$ and $A_{n+2}=A_n + A_{n+1}$ Thus $A_n = F_{n+2}$, the $(n+2)^{th}$ fibonacci number.

Answer 2

Supposing the subset is not the empty set we first choose the smallest value:

$$\frac{z}{1-z}.$$

Then we add in at least two several times to get the remaining values:

$$\frac{z}{1-z} \sum_{m\ge 0} \left(\frac{z^2}{1-z}\right)^m = \frac{z}{1-z} \frac{1}{1-z^2/(1-z)} = \frac{z}{1-z-z^2}.$$

Finally we collect the contributions that sum to at most $n$ and add one to account for the empty set:

$$1+ [z^n] \frac{1}{1-z} \frac{z}{1-z-z^2} \\ = [z^n] \frac{1}{1-z} + [z^n] \frac{1}{1-z} \frac{z}{1-z-z^2} \\ = [z^n] \frac{1}{1-z} \frac{1-z^2}{1-z-z^2} \\ = [z^n] \frac{1+z}{1-z-z^2}.$$

Calling the OGF $G(z)$ we have

$$G(z) (1-z-z^2) = 1 + z$$

so that for $[z^0]$ we get

$$[z^0] G(z) (1-z-z^2) = 1$$

or $g_0 = 1.$ We also get

$$[z^1] G(z) (1-z-z^2) = 1$$

or $g_1-g_0 = 1$ or $g_1=2.$ We have at the end for $n\ge 2$

$$g_n-g_{n-1}-g_{n-2} = 0,$$

which is the Fibonacci number recurrence. With these two initial values we obtain

$$\bbox[5px,border:2px solid #00A000]{ F_{n+2}.}$$