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

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

So

$$P(n)-P(n-1)=P(n-1)+P(n-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.