Recurrence relation related proof

Question

Find a recurrence relation for the number of ternary string that do not contain 00 or 11 .

Answer 1

If we define $T_i(n)$ as the number of ternary strings of length $n \geq 1$ ending in $i$, for $i \in \{0,1,2\}$, then we have $$T_0(n)=T_1(n-1)+T_2(n-1),$$ $$T_1(n)=T_0(n-1)+T_2(n-1), \text{ and}$$ $$T_2(n)=T_0(n-1)+T_1(n-1)+T_2(n-1)$$ for $n \geq 2$ (we append a $0$, $1$ or $2$, where allowed, to all possible strings of length $n-1$), and boundary cases: $T_i(1)=1$ for $i \in \{0,1,2\}$ and $T_0(2)=T_1(2)=2$ and $T_2(2)=3$.

If we define $$T(n)=T_0(n)+T_1(n)+T_2(n)$$ then substituting in the above gives \begin{align*} T(n) &= 2T_0(n-1)+2T_1(n-1)+3T_2(n-1) \\ &= 2T(n-1)+T_2(n-1) \\ &= 2T(n-1)+T(n-2). \end{align*}

This agrees with A078057 on the OEIS.