I have to find the number of subsets within the set 1, 2, 3, ....n that contain no two consecutive integers, where 0 and n also count as consecutive.
I have tried this proof where 0 and n do not count as consecutive, and I know it roughly follows the Fibonacci sequence, but it is the 0 and n part that is confusing me. Does this mean that the empty set and n are consecutive? And therefore the set containing just n is consecutive? I have seen questions like this where 1 and n count as consecutive, but the fact that I am asked to do this with 0 and n is confusing to me.
The more detail in explaining your answer the better. Thank you.
I assume that you here mean the set $\{ 0,1,2,3, \ldots, n\}$, since you refer to the number $0$.
The condition of being consecutive means that the successor relation is circular -- $1$ and $2$ are consecutive integers, but $n$ and $0$ are also consecutive integers. Consider as an example the universe $\{ 0,1,2,3,4 \}$. Here $\{1,3\}$ is a subset that does not contain any consecutive integers, whereas $\{3,4\}$ and $\{4,0\}$ are subsets that contain consecutive integers.
To find $S(n)$, the number of subsets of $\{ 0, \ldots, n\}$ that do not contain any consecutive integers, the most natural approach is to write down a recursive definition of $S(n)$.
Hint: A subset of $\{ 0, \ldots, n\}$ that does not contain any consecutive integers can be either a set of this kind chosen from the first $\{ 0, \ldots, n-1 \} $ or one that contains neither $0$ nor $n$.