I already had a look at the following problem: For a given set $\{1, \dots, n\}$, how many sets are there so that there are no two consecutive numbers in them?
The answer could be found by using recurrence relations, namely: $$ M_n = M_{n-1} + M_{n-2} + 1 - 1$$ where $M_{i}$ indicates the number of sets with ${i}$ being in them or not; $M_0 = 1$ and $M_1 = 2$ (having a look at those cases). It just means that if we omit $n$, we have $M_{n-1}$ options to choose, or we have as many choices as with $M_{n-2}$ (they are compatible with adding ${n}$ to them). $+1$ because of the set ${n}$, and $-1$ because the empty set will be in both recurrence relations used. I was able to calculate an explicit formula for $M_n$ by solving the recurrence relation.
Now I am stuck with solving the problem for $\{1,\dots, n\}$ being a cyclic set, meaning that $1$ is the successor of $n$.
Can someone give me a hint for finding a suiting recurrence relation?
Building on your result, you have $M_n=F_{n+2}$, the $n+2^{\text{nd}}$ Fibonacci number. To make a circle of $n$, you either include $n$, in which case you must have a linear subset of $\{2,3,4,\dots ,n-2\}$, or you do not include $n$, in which case you must have a linear subset of $\{1,2,3,4,\dots ,n-1\}$. Letting $C_n$ be the number of circular subsets out of $\{1,2,3,\dots n\}$, you have $C_n=M_{n-3}+M_{n-1}=F_{n-1}+F_{n+1}$