Find suitable recurrence relation 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$
 A: 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$.
A: 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
$$
