Recursive relationships for ternary strings

Question

If one were to have a ternary string with no repetition of consecutive $0$'s or $1$'s how would you define the recursive relation?

The first way I tried to solve was to assume $2$ was the last digit where we could have $a_{n-1}$ possible combinations due to no restrictions. For $1$ we can only have $01$ or $02$ and likewise for $0$ we can have $10$ or $20$ so the total strings possible for both is $4a_{n-2}$. I thought we would add it up to get $a_n= a_{n-1}+ 4a_{n-2}$.

This is the wrong answer and the other way I thought of solving it was to take into account that there can be any two possible last digit numbers for this to work for any possible $a_{n-1}$ string scenarios not including the $22$ combo which would be $a_{n-2}$. This gives the correct answer to be $a_n= 2a_{n-1}+a_{n-2}$. I was just wondering why my first reasoning doesn't match the second one. Thanks for your time Varun G.

Answer 1

Where you went wrong is that (for example) if your string ends in 0 you can indeed have the last two digits 10 or 20, and indeed 20 gives an unrestricted $n-1$ string before it, but for the 10 case you have a restriction on the $n-1$ string before it, namely that that substring can't end in 1. So you don't have $4 a_{n-2}$.

Answer 2

Let $A_n$ be the set of strings in $\{0,1,2\}^n$ not having $00$ or $11$ as substrings of consecutive characters, and $a_n=|A_n|$. Every element of $A_n$ is given by the concatenation of $2$ with an element of $A_{n-1}$, or by a concatenation of $02,12$ with an element of $A_{n-2}$, or by a concatenation of $012,102$ with an element of $A_{n-3}$, or by a concatenation of $0102,1012$ with an element of $A_{n-4}$ and so on. This gives:

$$ a_0=1,\quad a_1 =3,\quad a_2=7,\qquad a_{n}=a_{n-1}+2a_{n-2}+2a_{n-3}+\ldots+2a_{1}+2a_0+2.$$

Now, by induction, it is easy to check that: $$ a_{n+1} = 2a_n + a_{n-1} $$ so $a_n$ is given by the following OEIS entry.

Answer 3

If the last digit of a good $n$-digit string $\sigma$ is $2$, the string can indeed be an extension of any good string of length $n-1$. The problem is with your analysis of the other two cases.

If the last digit is $1$, there are two cases: either $\sigma$ ends in $21$, in which case the first $n-2$ digits can be any good string, or it ends in $01$. If it ends in $01$, it must end in $201$ or $101$ (assuming that $n\ge 3$, of course). If it ends in $201$, the first $n-3$ digits can be any good string. If it ends in $101$, however, and $n\ge 4$, then it must end in $2101$ or $0101$. Clearly we can keep going.

If you pursue this reasoning to the end, you’ll find that when the last digit is $1$ you have

$$a_{n-2}+a_{n-3}+\ldots+a_0+1\tag{1}$$

strings, where the last term counts the unique string of length $n$ that alternates $0$ and $1$ and ends in $1$. Essentially the same reasoning tells you that $(1)$ also counts the good strings of length $n$ ending in $0$, so you get the recurrence

$$a_n=a_{n-1}+2\left(1+\sum_{k=0}^{n-2}a_k\right)\;.$$

This isn’t terribly nice, but you can use it to get the second-order recurrence that your second approach gave you. First note that

$$a_{n-1}=a_{n-2}+2\left(1+\sum_{k=0}^{n-3}a_k\right)\;.$$

Thus,

$$\begin{align*} a_n&=a_{n-1}+2\left(1+\sum_{k=0}^{n-2}a_k\right)\\ &=a_{n-1}+2a_{n-2}+2\left(1+\sum_{k=0}^{n-3}a_k\right)\\ &=a_{n-1}+a_{n-2}+\left(a_{n-2}+2\left(1+\sum_{k=0}^{n-3}a_k\right)\right)\\ &=a_{n-1}+a_{n-2}+a_{n-1}\\ &=2a_{n-1}+a_{n-2}\;. \end{align*}$$