Let $\Sigma_{2}$ be the space of all sequences such that $s = (s_{0}, s_{1}, \ldots)$ with $s_{\iota} = 0$ or $s_{\iota} = 1$ i.e. all sequences consisting of only $1$'s and $0$'s.
Define the shift map $\sigma : \Sigma_{2} \rightarrow \Sigma_{2}, s \mapsto \sigma(s) = (s_{1}, s_{2}, \ldots)$. I.e. the shift map "forgets"/removes the first point in the sequence.
Let $\Sigma'$ be the space of all sequences in $\Sigma_{2}$ such that if $s_{\iota} = 0$, then $s_{\iota + 1} = 1$. I.e. there are no two consecutive zeros in the sequence. And now we restrict the shift map $\sigma$ to $\Sigma'$ and the question below refers to $\sigma$ being restricted to $\Sigma'$.
Find a recursive formula for the number of fixed points of $\sigma^{n}$ in terms of the number of fixed points of $\sigma^{n - 1}$ and $\sigma^{n - 2}$. Here, $\sigma^{n} = \sigma \circ \sigma \circ \ldots \circ \sigma$ i.e. the nth composition of sigma with itself.
What I have done:
For $n = 1$ we want $\sigma(s) = s$ for $s \in \Sigma'$. I.e. we want $(s_{1}, s_{2}, \ldots) = (s_{0}, s_{1}, s_{2}, \ldots)$. And this is true if and only if $s_{\iota} = s_{\kappa}$ where $\iota = \kappa + 1$ for $\kappa \in \mathbb{N} = \{ 0, 1, 2, \ldots \}$. So it must be that $s_{1} = s_{0}$, $s_{2} = s_{1}$ and so on.
Now, since $s \in \Sigma'$ a problem might occur if at least one $s_{\iota} = 0$ because then $s_{\iota + 1} = 1$ and hence we would then have i.e. $s_{3} \neq s_{4}$. So my answer seems to be that none of the points in the sequence should equal to $0$. So is there then only one fixed point? i.e. the sequence $(1, 1, 1, \ldots)$? Because we have here that $s_{\iota} = s_{\iota + 1}$ must be true and this is not true by the condition of the space $\Sigma'$ if $s_{\iota} = 0$.
For $n = 2$ we then would want $\sigma^{2}(s) = \sigma(\sigma(s)) = (s_{2}, s_{3}, \ldots) = s = (s_{0}, s_{1}, s_{2}, \ldots)$. And here we would want $s_{2} = s_{0}$, $s_{3} = s_{1}$, etc. Here for instance as a fixed points the sequence $(1, 1, 1, \ldots )$ will work. And so will $(0, 1, 0, 1, \ldots)$. Also $(1, 0, 1, 0, \ldots)$; since now we want $s_{\iota} = s_{\iota + 2}$.
And for arbitrary $n$ we would want $s_{n} = s_{0}$, $s_{n + 1} = s_{1}$, etc.
So it seems that the problem occurs when we have a $0$ in the sequence. And I am unsure how many fixed points there are and how to recursively relate the iterations with one another.
Since $\sigma^n$ translates the sequence by $-n$, any sequence fixed by it is completely determined by the first $n$ elements. Every subsequent string of $n$ elements must be identical, or else the shift would change the sequence. On the other hand, any sequence of $n$ elements provides a fixed sequence by repeating the initial elements: $\forall i, s_i = s_{i\bmod n}$.
So the question becomes: how many sequences of $n$ elements are there such that no two $0$s are adjacent (where the first and last elements are considered to be adjacent). This is a problem in combinatorics.
Ignore for the moment the need for the first and last elements to not both be $0$. Let $z_n$ be the number of such strings ending in $0$, and $o_n$ be the number ending in $1$. Suppose you remove the last two elements of such a string. The remaining $n-2$ length string will either be one of the $z_{n-2}$ strings ending in $0$, or the $o_{n-2}$ strings ending in $1$. If it ends in $0$, then the removed bits are either $10$ or $11$. If it ended in $1$, the removed bits are either $10, 11,$ or $01$. $$o_n = 2o_{n-2} + z_{n-2}\\z_n = o_{n-2} + z_{n-2}$$ Now if an $n$-length string begins and ends with $0$ ($n \ge 3$), it must begin with $01$ removing this initial $01$ leaves a string of length $n-2$ that ends in $0$. Conversely adding $01$ to the front of any $n-2$-string ending in $0$ results in an $n$-string beginning and ending in $0$. Thus there are exactly $z_{n-2}$ strings of length $n$ that both begin and end in $0$. So the total number of strings without adjacent $0$s where the first and last elements are adjacent is $a_n := o_n + z_n - z_{n-2}$
Now you could figure out the recursion using various methods, but noting by inspection that $o_1 = 1, z_1 = 1$ while $o_2 = 2, z_2 = 1$ and just calculating a few terms gives
$$\begin{array} {c|c|c|c} n&o_n&z_n&a_n\\\hline 1&1&1&2\\2&2&1&3\\3&3&2&4\\4&5&3&7\\5&8&5&11\\6&13&8&18\end{array}$$ From which it is evident that $o_n = F_{n+1}, z_n = F_n$ and $a_n = F_{n+2} - F_{n-2}$ ($n \ge 3$), where $\{F_n\}$ are the Fibonacci numbers (though I'll leave the actual proof to you).