Find suitable recurrence relation

Question

So I need to find a correct recurrence relation to this problem:

How many series of size n over {0,1,2} exist, so that each digit never appears alone. For example, this series is good: 000110022, and this series is bad: 000122.

I did find a correct relation: $f(n) = f(n-1) + 2*f(n-2)$ or $f(n) = 3*f(n-2) + 2*f(n-3)$ (both work. But I have no idea how to explain them. I found them just by brute force.

I would think that $f(n) = 3*f(n-2) + 3*f(n-3)$ minus the intersection between the two, but again it seems as though that intersection is $f(n-3)$ (according to the above relation), and I have no idea why.

Any help would be appreciated. Thanks!

P.S. $f(1) = 0, f(2)=3, f(3)=3, f(4)=9, f(5)=15$

Answer 1

Call the number of sequences of length $n$ as described $a_n$. We know $a_2 = 3$ and $a_3 = 3$ (they must be formed by one symbol type only).

A sequence of length $n$ is made of a sequence of length $n - 1$ by adding another symbol as the last one (1 way), or out of one of length $n - 2$ by adding two symbols different from the last one (2 ways): $$ a_n = a_{n - 1} + 2 a_{n - 2} \qquad a_2 = a_3 = 3 $$

Answer 2

For simplification, consider only the number $F_n$ of legal strings that end with a fixed symbol $l\in\{0,1,2\}$ (your original series is then just $f_n=3F_n$).

For example for $n=5$ you count strings of the form

$$???ll,\quad ??lll,\quad ?llll,\quad lllll$$

Where the last $?$ is always $\neq l$.

This can be written as $$F_n = K_{n-2} + K_{n-3} + ... + K_1 + 1.$$

where $K_n$ counts the legal length-$n$ strings, that do not end with $l$, i.e. those $????$-strings from above. As they can only end with two other symbols, we have

$$K_n=2F_n$$ and we find

$$F_n=2F_{n-2} + 2F_{n-3} +...+2F_1+1$$

Now with this formula you find that

$$F_{n}=2F_{n-2}+F_{n-1}.$$

As we mentioned before, $f_n=3F_n$, hence the same recursion holds for $f_n$.