Recursion for the number of words of length $n$ over the alphabet $\{0, 1, 2\}$ such that there are neither $11$ nor $22$ blocks

Question

Let $a_n$ be the length of words over an alphabet $\{0,1,2\}$ such that there are neither $11$ nor $22$ "blocks".

I. e. $001020$ would be allowed, $001120$ wouldn't because we have a $11$ block.

I have to show that $$a_n=2a_{n-1}+a_{n-2}$$

It looks like this recursion dissects the question into three cases (and adds them all up):

• The word of length $n$ ending with $0$: We have: $\underbrace{\cdots \cdots \cdots }_{a_{n-1}}0$
• The word of length $n$ ending with $1$: We have $\cdots \cdots \cdots 1$. Now we'll have to be careful though, since the digit that preceeds $1$ can't be $1$. It has to be a $0$ or a $2$. Do I have to distinguish these cases as well? Say, it is $0$, then $\underbrace{\cdots \cdots \cdots}_{a_{n-2}} 01$. Likewise if it was $2$. How do I take into account this ambiguity?
• The word of length $n$ ending with $2$ is essentially the same as the one ending with $1$.

It would make sense to me if it'd be $a_n=a_{n-1}+2\cdot a_{n-2}$.

Answer 1

Define $b_n$ to be the number of acceptable sequences ending in $0$, $c_n$ the number ending in $1$, and $d_n$ be the number ending in $2$, so we have $a_n = b_n+c_n+d_n$. A $0$ can follow any digit, a $1$ can only follow a $0$ or $2$, and a $2$ can only follow a $0$ or $1$, so $$\begin{align} b_n &= b_{n-1} + c_{n-1} + d_{n-1} \tag{1} \\ c_n &= b_{n-1} + d_{n-1} \tag{2} \\ d_n &= b_{n-1} + c_{n-1} \tag{3} \end{align}$$ Adding $(1)$, $(2)$ and $(3)$, $$\begin{align} b_n+c_n+d_n &= 3b_{n-1} + 2c_{n-1} + 2d_{n-1} \\ a_n &= 2a_{n-1} + b_{n-1} \\ \end{align}$$ Applying $(1)$ with $n$ replaced by $n-1$, $$\begin{align} a_n &= 2a_{n-1} + b_{n-2} + c_{n-2} + d_{n-2} \\ &= 2a_{n-1} + a_{n-2} \end{align}$$

Answer 2

$\color{blue}{\text{Case I-)}}$ It start up with $0$:

• $0...\rightarrow a_{n-1}$

This is obvious , as you wrote , it is $a_{n-1}$

$\color{blue}{\text{Case II-)}}$

For each $k$ between zero and $(n-2)$ , there could be string of $(n-k-1)$ alternating $1's$ and $2's$ which followed by a zero , so followed by no pair of consecutive ones or twos.Then there are $2a_{n-(n-k)}=2a_k$ such strings.For example:

• $20.... \rightarrow a_{n-2}$

• $10.... \rightarrow a_{n-2}$

• $120.... \rightarrow a_{n-3}$

• $210.... \rightarrow a_{n-3}$

• $121212.... \rightarrow a_{0}$

• $212121.... \rightarrow a_{0}$

So , $$2a_{n-2}+2a_{n-3}+....+2a_{0}$$

$\color{blue}{\text{Case III-)}}$

Ternary strings that always alternate bewtween $1$ and $2$ , we have two such strings such that

• $121212....$

• $212121...$

So we have two such strings.

Now , lets sum these three cases to reach $a_n$ such that $$a_n=(a_{n-1})+(2a_{n-2}+2a_{n-3}+....+2a_{0})+2$$

However , we cannot find any value using this long recursion ,so lets make a manipulation such that $$a_{n-1}=(a_{n-2})+(2a_{n-3}+2a_{n-4}+....+2a_{0})+2$$

Now , lets subtract them such that

$$a_n=(a_{n-1})+(2a_{n-2}+2a_{n-3}+....+2a_{0})+2$$

$$a_{n-1}=(a_{n-2})+(2a_{n-3}+2a_{n-4}+....+2a_{0})+2$$

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

So , $$a_n=2a_{n-1}+a_{n-2}$$

Answer 3

It is always fine if the last two digits are different. We always have two choices for the next digit. That gives $2a_{n-1}$. But we can also end with $00$. That gives $a_{n-2}$.