Let \(b(n)\) be the number of binary strings of length \(n\) not containing 101. This means that all bit strings of length 1 and 2 satisfy the criterion, and only one bit string (101) of length 3 fails to satisfy it. This gives us initial conditions of
\begin{equation*}
b(1) = 2\qquad b(2) = 4 \qquad b(3) = 7\text{.}
\end{equation*}
If the first digit of a bit string of length \(n\) is 0, then the remaining \(n-1\) positions can be filled with any of the \(b(n-1)\) bit strings of length \(n-1\) that do not contain 101. If the first digit of a 101-avoiding bit string of length \(n\) is a 1, then the remaining \(n-1\) positions can be filled with any 101-avoiding bit string of length \(n-1\) that does not start with 01. There are \(b(n-1)\) bit strings of length \(n-1\) that avoid 101. Since we are only thinking now about those bit strings that we know don’t contain 101, we are looking to subtract those that start with 01.
Our task now is to count the 101-avoiding bit strings of length
\(n-1\) that start 01, so we can subtract as discussed in the previous paragraph. To do this, notice that there is a one-to-one correspondence between 101-avoiding bit strings of length
\(n-1\) that start 01 and 101-avoiding bit strings of length
\(n-2\) that start with 1. (Removing the 0 from the length
\(n-1\) bit string gives a length
\(n-2\) bit string of the type required, and taking a length
\(n-2\) bit string that avoids 101 and starts with 1 and adding a 0 to the front gives a 101-avoiding bit string of length
\(n-1\) that starts 01.)
OK, so now what we really want to count (so we can subtract it!) is the number of 101-avoiding bit strings of length
\(n-2\) that start with 1. Since every 101-avoiding bit string of length
\(n-2\) either starts with a 0 or a 1, adding the number that start with 0 to the number that start with 1 yields
\(b(n-2)\text{.}\) Alternatively, the number of 101-avoiding bit strings of length
\(n-2\) that start with 1 can be found by taking
\(b(n-2)\) and subtracting the number of 101-avoiding bit strings of length
\(n-2\) that start with 0.
OK, so what we really need to count (and then we’ll see how to use it!) is the number of 101-avoiding bit strings of length
\(n-2\) that start with 0. But as we saw before, we can turn any 101-avoiding bit string of length
\(n-2\) that starts with 0 and turn it into a 101-avoiding bit string of length
\(n-3\) by removing the leading 0. Conversely, we can take any 101-avoiding bit string of length
\(n-3\) and put a 0 on its front without creating 101, so then we have a 101-avoiding bit string of length
\(n-2\) that starts with 0. Therefore, the number of 101-avoiding bit strings of length
\(n-2\) that start with 0 is the same as the number of 101-avoiding bit strings of length
\(n-3\text{,}\) which we know to be
\(b(n-3)\text{.}\) Progress!
Alright, so here’s a summary of where we are:
\begin{align*}
b(n) \amp = b(n-1) + \left[b(n-1) - (\text{length }n-1\text{ start }01)\right]\\
(\text{length }n-1\text{ start }01)\amp = (\text{length }n-2\text{ start }1) \\
(\text{length }n-2\text{ start }1)\amp = b(n-2) - (\text{length }n-2\text{ start }0)\\
(\text{length }n-2\text{ start }0) \amp = b(n-3)\text{.}
\end{align*}
Now we’ve got all the information we need to substitute in, so we have
\begin{align*}
(\text{length }n-2\text{ start }1)\amp = b(n-2) - b(n-3)\\
(\text{length }n-1\text{ start }01)\amp = b(n-2) - b(n-3) \\
b(n) \amp = b(n-1) + \left[b(n-1) - (b(n-2) - b(n-3) )\right]\\
\amp = 2b(n-1) - b(n-2) + b(n-3)\text{.}
\end{align*}
Thus, \(b(n) =2b(n-1) - b(n-2) + b(n-3) \) for \(n\geq 4\) with \(b(1)=2\text{,}\) \(b(2) = 4\text{,}\) and \(b(3)=7\text{.}\)
