Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s.

Note: Problem from "Kenneth Rosen's DM and it's applications" and solution from "Students solution guide for use with ... applications"

Let P(n) be the number of strings not containg two containing two consecutive zeros or two consecutive ones.

I got the answer P(n)=P(n-1)+2P(n-2)+2P(n-3)+...+2P(0) +2

but then the book says the sequence also satisfies the recurrence relation P(n)=2P(n-1)+P(n-2). I am not able to understand this part.

Solution 1:

$$P(n-1)=P(n-2)+2P(n-3)+\dots+2$$

So

$$P(n)-P(n-1)=P(n-1)+P(n-2)$$

Solution 2:

You can think about it like this: start with a string of length $n-1$. It's last character is $x\in \{0, 1, 2\}$. If $x=0$ or $x=1$, then you have $2$ choices for how to finish (either $\{1, 2\}$ if $x=0$ or $\{0, 2\}$ if $x=1$). If $x=2$ then we have $3$ choices for how to finish: $\{0, 1, 2\}$. Let's think about what the end of strings look like. I'll let $x_{0}$ denote that the $n-1$st element is a $0$, $x_{1}$ to denote that the $n-1$st element is a $1$ and $x_{2}$ to denote that the $n-1$st element is a $2$. Strings could end in any of the following ways:

$x_0 1$

$x_0 2$

$x_1 0$

$x_1 2$

$x_2 2$

$x_2 1$

$x_2 0$

Note that if I group the first 6 of these, I have counted $2P(n-1)$ strings; this is because every one of the strings of length $n-1$ either ends in a $0$, $1$ or a $2$ and I've counted each of those occurrences twice. And, I still need to count the strings that end in $x_2 0$ (or the last two digits are $2,0$). The number of ways to end in $2,0$ is precisely $P(n-2)$ since I can append $2,0$ to any string of length $n-2$. Thus all together there are $2P(n-1)+P(n-2)$ strings that fit your criteria.