1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I suggest you to improve formatting by using $\LaTeX$. $\endgroup$ – Jack D'Aurizio Feb 15 '15 at 23:20
0
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.