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

Let $b_n$ be the number of $n$-digit ternary strings which begin with $0$ and contain neither $00$ nor $11$. Let $c_n,d_n$ be the same except starting with $1$ or $2$ respectively. Let $$t_n=b_n+c_n+d_n$$ be the total number of $n$-digit ternary strings which contain neither $00$ nor $11$. What you want is $$a_n=3^n-t_n\ .$$ To find a recurrence for $b_n$ observe that an $n$-digit ternary string which begins with $0$ and contains neither $00$ nor $11$ is

• $0$, followed by an $(n-1)$-digit string which begins with $1$ and contains neither $00$ nor $11$; or
• $0$, followed by an $(n-1)$-digit string which begins with $2$ and contains neither $00$ nor $11$.

Therefore $$b_n=c_{n-1}+d_{n-1}\ ;$$ similar arguments give $$c_n=b_{n-1}+d_{n-1}$$ and $$d_n=b_{n-1}+c_{n-1}+d_{n-1}=t_{n-1}\ .$$ Adding all of these gives $$t_n=2t_{n-1}+d_{n-1}$$ and so $$t_n=2t_{n-1}+t_{n-2}\ .$$ Writing in terms of $a_n$, we have $$3^n-a_n=2(3^{n-1}-a_{n-1})+(3^{n-2}-a_{n-2})$$ which simplifies to $$a_n=2a_{n-1}+a_{n-2}+2\times3^{n-2}\ .$$