# Solve recurrence for strings that do not contain the substring 101

Let's say $$A_n$$ is the number of binary string that has length $$n$$ and does not contain the substring 101. Calculate $$A_n$$ for $$n=1,2\cdots8.$$ Find a recurrence relation for $$A_n$$. What does the solution of that recurrence look like?

These are the solutions that I have found for calculations for $$A_n$$. $$1, 4, 7, 12, 20, 32, 48, 96$$.

I've calculated this by hand. But how I do find the recurrence? I see that 4, 7, 12, 30 are Fibonacci - 1, but not after or before that.

But I'm not sure how to do this or if this is even correct.

• I think your values may be counting the complement; those strings that DO contain $101$, no? – lulu Dec 9 '18 at 12:09
• Many similar questions have been asked on the site...this question for instance. – lulu Dec 9 '18 at 12:10
• You should double check your values of $A_n$, they are all wrong. A hint: if you are having trouble getting a recurrence, let $B_n$ be strings avoiding 101 which end in 0, an let $C_n$ be strong avoiding 101 ending in 1, then get a mutual recurrence for those. – Mike Earnest Dec 9 '18 at 17:12
• Thank you. I've edited my question to add the correct solution, but I'm still not sure how to find and solve the recurrence? – ponikoli Dec 10 '18 at 19:15
• Try to proceed similarly to this answer. – Alex Ravsky Dec 11 '18 at 5:30

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*}

• +1 Your answers (not just this one) are so good and clear, there needs to be a SUBSCRIBE button. :) – antkam Mar 26 at 14:06
• @antkam: Many thanks for your nice comment. It's good to see the answer is useful. :-) – Markus Scheuer Mar 26 at 15:09