Suppose I have a binary string of length $n$ with the only permissible characters $0$ and $1$. The string is supposed to follow the constraint that adjacent to every character must be a $0$, either to the left, or the right, or both.
I denote by $S_n$ the number of strings of length $n$ that follow the aforementioned criteria. How can I evaluate $S_n$ for somewhat larger values such as say $13$? Is a closed form expression possible for $S_n$?
My work
I couldn't make any progress on this, but it is clear that for the condition to follow for a string of length $n$, the $2$nd and $(n-1)$th digits must both be $0$. The evaluation becomes rather simple for smaller $n$ such as $S_3 = 3$, $S_4 = 4$, $S_5=4$, $S_6=9$ etc. But I am struggling to find any way to evaluate something like $S_{13}$.
Any help is appreciated.
To find these values by hand you can use the concept of dynamic programming.
Lets first denote the following expressions:
$S_{n, 0}$ - number of valid sequences of length $n$ starting with $0$
$S_{n, 1}$ - number of valid sequences of length $n$ starting with $1$
$S_{n}$ - number of valid sequences of length $n$
Obviously $S_n = S_{n, 0} + S_{n, 1}$
Let's observe that any such sequence must have $0$ as the second digit.
If sequence of length $n$ begins with $1$ then the remaining part of the sequence must be valid sequence of length $n - 1$ and must begin with $0$. So: $$S_{n, 1} = S_{n-1, 0}$$
Furthermore if sequence of length $n$ begins with $0$ then we can have two cases.
Case $1$: third digit of the sequence is equal to $0$
We can easily denote that the number of such sequences is equal to $S_{n-1, 0}$, becuase apart from starting $0$ the remainig part must form valid sequence of lentgh $n-1$ that starts with $0$.
Case $2$: third digit of the sequence is equal to $1$
We can observe that, this $1$ already has adjacent $0$ so we can say that remaining part of the sequence (apart from the first three digits) must form valid seqeunce of length $n-3$ and there are $S_{n-3}$ such sequences.
So we can denote: $$S_{n, 0} = S_{n-1, 0} + S_{n-3}$$
If we now take everything together we will get: $$S_n = S_{n, 0} + S_{n, 1} = S_{n-1, 0} + S_{n-1, 0} + S_{n-3} = 2S_{n-1, 0} + S_{n-3}$$
To efficiently calculate those values we can store these results in a table: $$ \begin{array}{|c|c|c|c|c|} \hline n & 3 & 4 & 5 & 6 & 7 & \cdots & \cdots & \cdots & \cdots \\ \hline S_{n, 0} & 2 & 2 & 3 & 6 & 10 & \color{red}{15}& \\ \hline S_{n-2} & ? & ? & 3 & 4 & 5 & 9 & 16 & \color{green}{25}&\\ \hline \end{array} $$ To fill up the table you have to first find the value of first row by adding values in previous column (here you get $10 + 5 = 15$) and then you can find the value in the second row by adding to previously achieved result value from the second last cell in the first row (here $15 + 10 = 25$). Notice that there is a shift applied for the values of $S_n$ beacuse now you can fill the table in more convenient way.