Check proof of recurrence for the number of ternary strings of length n that contain 00, 11, or 22

Question

The question:

Find a recurrence for the number of n length ternary strings that contain "00", "11", or "22".

My answer:

$3(a_{n-2}) + 3(a_{n-1} - 1)$

Proof:

Cases:

______________00 (a_(n-2))

______________11 (a_(n-2))

______________22 (a_(n-2))

______________0 (a_(n-1) - 1)

______________1 (a_(n-1) - 1)

______________2 (a_(n-1) - 1) (Subtract the case in which it ends with 00, 11, or 22)

Answer 1

Let's see: $a_0 = 0$, $a_1 = 0$, $a_2 = 3$. No, that's not $3 a_0 + 3 (a_1 - 1)$.

Answer 2

Your first mistake is this: $$ \underline{\qquad\qquad}00 \quad (a_{n-2}) $$ You seem to be assuming that no string that ends in $00$ should be counted unless it also contains $00$, $11$, or $22$ somewhere earlier in the string.

For example, for $n=6$, you do not count the string $012100$, because the first four digits $0121$ are not among the $a_4$ strings of length $4$ that contain $00$, $11$, or $22$.