Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

Question

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this recursive function? I have an exam on Thursday and I am struggling with the concept of finding the recursive definition for strings. Can someone explain how this works and give few examples to make it clear? Thank you.

Answer 1

Given a string of length $n-1$, you can add any of $0$, $1$, or $2$ to the end of it to get a string of length $n$, so you get $3 a(n-1)$ strings. However, if the last two elements of the original string were $01$, then adding $2$ is not allowed. How many such strings are there? Well, they are found by noting that after removing the $01$ you have an arbitrary string of length $n-3$. So you must subtract $a(n-3)$ to avoid counting these.

More visually, \begin{align*} \underbrace{...0}_{n-1} &\quad\Rightarrow\quad ...00,\ ...01,\ ...02 \\ \underbrace{...1}_{n-1} &\quad\Rightarrow\quad ...10,\ ...11,\ ...12 \\ \underbrace{...2}_{n-1} &\quad\Rightarrow\quad ...20,\ ...21,\ ...22 \end{align*} so that every length $n-1$ string gives nine length $n$ strings. If the original string didn't contain $012$, neither will the new one, except for the last entry on the second row. If that length $n-1$ string ended in $01$, then we will have created a $012$ in the new string. But if that string ended in $01$, then the other digits in the string (there are $n-3$ of them) are arbitrary. So there are $a(n-3)$ ways in which we could have erroneously added the $012$. We must subtract that to get the right answer.

So for example $a(3) = 3a(2) - a(0) = 26$, $a(4) = 3a(3) - a(1) = 75$.

Answer 2

$a_n=2a_{n-1}+b_{n-1}$

$b_n=b_{n-1}+c_{n-1}+a_{n-1}$

$c_n=a_{n-1}+b_{n-1}$

---

Explanation:

-First relation:

$2a_{n-1}$ indicates sequences starting by 1... or 2... while the relation $a$ is for unconstrained sequences

$b_{n-1}$ indicates 0... while $b$ is a sequence right-bounded by a $0$

-Second relation:

$c_{n-1}$ indicates 01... while $c$ is any sequence right-ended by $0...1$

$b_{n-1}$ indicates 00... while $a_{n-1}$ indicates 02...

-Third relation:

$a_{n-1}$ indicates 011... and $b_{n-1}$ points to 010...

---

Example:n=3 (xxx)

Naive enumeration says $S=3*3*3-1=26$ where the subtracted case is 210

Recursive enumeration:

$a_3=2a_2+b_2=2(2a_1+b_1)+b_2=2(2(2a_0+b_0)+b_1)+b_2=8a_0+4b_0+2b_1+b_2$

$b_1=b_0+c_0+a_0=3$

$b_2=b_1+c_1+a_1$

$c_1=a_0+b_0=2$

$a_1=3$

$b_2=3+2+3=8$

$a_3=8+4+8+6=26$

---

Example2:n=4 (xxxx)

-From informations above, $a_3=26,a_2=9,b_2=8,a_1=3,b_1=3$

$a_4=2a_3+b_3=2*26+b_3$

$b_3=b_2+c_2+a_2=8+c_2+9$

$c_2=b_1+a_1=3+3=6$

$b_3=23$

$a_4=52+23=75$ which matches previous results.