Recurrency is ok but if part is complicated

Question

How many subsets does the set $\{1,2,\ldots,n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive?

Answer 1

Here is a way to compute this.

Let $X_n$ be the number of independent sets of a simple path on $n$ vertices. For $n=0$, the only independent set is the empty set, so $X_0=1$. For convenience, we define $X_n = 1$ for $n<0$ as well. For $n>0$, either we include the first vertex and exclude the second, leaving $n-2$ vertices, or we exclude the first vertex, leaving $n-1$ vertices. This gives us: $$ X_n = \left\{ \begin{array}{ll} 1 & n \leq 0 \\ X_{n-2} + X_{n-1} & n \gt 0 \\ \end{array} \right. $$

Let $Y_n$ be the number of independent sets of a simple cycle on $n>0$ vertices. Designate some "starting vertex". Then we either include the starting vertex (leaving a path of $n-3$ vertices), or we don't (leaving a path of $n-1$ vertices). So: $$Y_n = X_{n-3} + X_{n-1}$$

Edit: Wow, I just noticed that for $n\geq-1$, $X_n$ is in fact the $(n+1)$^th Fibonacci number! That probably explains the relation to $\phi$ on OEIS.

Answer 2

If you take a (numbered) $n\times1$ strip and count the number of ways to tile it with squares and dominoes, you get the standard Fibonacci numbers. If you wrap the strip around into a circle and do the same, then, except when $n=1$, you get the sequence A169985 that Ross Millikan noted in comments. For $n\not=1$, there is a one-to-one correspondence between tilings and subsets with no consecutive numbers: for each domino in a tiling, let the subset include the smaller of the two numbers covered by the domino (where $n$ is considered "smaller" than $1$), and vice versa.

The case $n=1$ is special in that the only way to tile a $1\times1$ wrap-around strip is with a square, but there are obviously two subsets satisfying the non-consecutivity condition, $\emptyset$ and $\{1\}$.

(The case $n=2$ might also be considered special, depending on how you count the number ways to place the domino. I'm viewing it as having two options.)