Solve recurrence for strings that do not contain the substring 101

Solution 1:

We count the number $a(n)$ of valid binary strings, i.e. strings which do not contain $101$ by partitioning them according to their matching length with the initial parts of the bad string $101$.

\begin{align*} a_n=a^{[\emptyset]}_n+a^{[1]}_n+a^{[01]}_n\tag{1} \end{align*}

• The number $a^{[\emptyset]}_n$ counts the valid strings of length $n$ which do not start with the rightmost character of the bad word $10\color{blue}{1}$, i.e. start with $0$.

• The number $a^{[1]}_n$ counts the valid strings of length $n$ which do start with the rightmost character of the bad word $10\color{blue}{1}$, i.e. $\color{blue}{1}$.

• The number $a^{[01]}_n$ counts the valid strings of length $n$ which do start with the two rightmost characters of the bad word $1\color{blue}{01}$, i.e. start with $\color{blue}{01}$.

We get a relationship between valid strings of length $n$ with those of length $n+1$ as follows:

• If a word counted by $a^{[\emptyset]}_n$ is appended by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.

• If a word counted by $a^{[1]}_n$ is appended by $0$ from the left it contributes to $a^{[01]}_{n+1}$. If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.

• If a word counted by $a^{[01]}_n$ is appended by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$. Appending from the left by $1$ is not allowed since then we have an invalid string starting with $101$.

This relationship can be written as \begin{align*} a^{[\emptyset]}_{n+1}&=a^{[\emptyset]}_{n}+a^{[01]}_{n}\tag{2}\\ a^{[1]}_{n+1}&=a^{[\emptyset]}_{n}+a^{[1]}_n\tag{3}\\ a^{[01]}_{n+1}&=a^{[1]}_n\tag{4} \end{align*}

We can now derive a recurrence relation from (1) - (4):

We obtain for $n\geq 3$: \begin{align*} \color{blue}{a_{n+1}}&=a^{[\emptyset]}_{n+1}+a^{[1]}_{n+1}+a^{[01]}_{n+1}\tag{$ \to (1)$}\\ &=\left(a^{[\emptyset]}_{n}+a^{[01]}_{n}\right)+\left(a^{[\emptyset]}_{n}+a^{[1]}_n\right)+\left(a^{[1]}_n\right)\tag{$\to (2),(3),(4)$}\\ &=2a_n-a^{[01]}_{n}\tag{$\to (1)$}\\ &=2a_n-a^{[1]}_{n-1}\tag{$\to (4)$}\\ &=2a_n-a_{n-2}+a^{[\emptyset]}_{n-2}+a^{[01]}_{n-2}\tag{$\to (1)$}\\ &=2a_n-a_{n-2}+a^{[\emptyset]}_{n-3}+a^{[01]}_{n-3}+a^{[1]}_{n-3}\tag{$\to (2),(4)$}\\ &\,\,\color{blue}{=2a_n-a_{n-2}+a_{n-3}}\tag{$\to (1)$} \end{align*}

We finally derive manually the starting values

\begin{align*} \color{blue}{a_0=1,a_1=2,a_2=4,a_3=7} \end{align*}

and obtain a sequence $(a_n)_{n\geq 0}$ starting with \begin{align*} (a_n)_{n\geq 0}=(1,2,4,7,12,21,37,65,114,200,351,\ldots) \end{align*}

Hint: We have $a_5=\color{blue}{21}$ valid strings of length $5$. The $2^5-21=11$ invalid strings are \begin{align*} \color{blue}{101}00\qquad0\color{blue}{101}0\qquad00\color{blue}{101}\\ \color{blue}{101}01\qquad0\color{blue}{101}1\qquad01\color{blue}{101}\\ \color{blue}{101}10\qquad1\color{blue}{101}0\qquad\color{lightgrey}{10101}\\ \color{blue}{101}11\qquad1\color{blue}{101}1\qquad11\color{blue}{101} \end{align*}