2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think your values may be counting the complement; those strings that DO contain $101$, no? $\endgroup$ – lulu Dec 9 '18 at 12:09
  • $\begingroup$ Many similar questions have been asked on the site...this question for instance. $\endgroup$ – lulu Dec 9 '18 at 12:10
  • $\begingroup$ 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. $\endgroup$ – Mike Earnest Dec 9 '18 at 17:12
  • $\begingroup$ 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? $\endgroup$ – ponikoli Dec 10 '18 at 19:15
  • $\begingroup$ Try to proceed similarly to this answer. $\endgroup$ – Alex Ravsky Dec 11 '18 at 5:30
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.