Recurrence relation for binary strings of length $n$ that doesnt contain $010$ pattern?

Question

I've looked up this question in here and found one whose answer didnt look complete to me or maybe I couldnt figure it out correctly.. I can understand the first part of the answer $a_n = a_{n-1} + a_{n-3} + a_{n-4} + a_{n-5} + \cdots + a_{1} + 3$ But my problem mosly is on last part $a_1 + 3$ Any help like "explanation for dummies" kind of answer would be great ! What is the best approach to analyze these kinda problems .. The related link: $n$-Bit Strings Not Containing $010$ Thanks a lot !

Answer 1

I think understanding the $+ 3$ revolves around understanding the first bits so bare with me as I explain my interpretation. First, keep in mind that if we have a "good" string (one that meets the given requirements) of length $n-1$ and append a $1$ to the start, we will always get a "good" string of length $n$, since adding a $1$ to the front can't create an occurrence of $010$. This contributes the $S_{n-1}$ term.

However, the string needn't necessarily begin with $1$. It could start with some string of $0$'s. Now, we assume two things: the first is that the string of $0$'s is followed by $11$ and secondly, that the $11$ is followed by a good string. This is because we know that if $1$ follows a $0$ in the string, then to make it a good string, that $1$ must be followed by another $1$. Then, we'll have something of the form $000...011$+[good string]. Then since $010$ occurs in neither of the concatenated strings, nor in the part where they meet, then the result is a good string. Thus, we begin with $011$+[good string of length $n-3$] contributing $S_{n-3}$, $0011$+[good string of length $n-3$] contributing $S_{n-4}$, and so on until we get to a string of $n-3$ $0$'s, $11$ and then $0$ or $1$, which is counted by $S_{1}=2$.

Now we consider the exceptions: as I said before, we assume, among other things, that there is something following the $11$ buffer. However, we could have $00...011$, which is a good string. We also might not even have the $11$ buffer: we can also have $00...01$ and $00...0$. In these cases, the complete buffer is not necessary. However, in any other case where we have a string of $0$'s followed by $1$ followed by at least $2$ entries, then we refer to the previous cases.