Finding the recurrence relation. So the question has 2 parts to it.
Let $f(n)$ be  the number of sequences in length n that are built of 0, 1, and 2, so that after zero there's always 1 right after it. 
Let $g(n)$ be the number of sequences in length n that are built of 0, 1 and 2, so that between two 2's in the sequence theres 0. (not necessarily right after it)
I need to find recurrence relations for $f(n)$ and $g(n)$.
I need some hints or ideas, thanks in advance.
 A: For $f$: If the first digit is a 0, then necessarily the second one is a 1. The remaining part is an arbitrary legitimate sequence of length $n-2$.
If the first digit is a 1 or a 2, the remaining part is an arbitrary legitimate sequence of length $n-1$. So
$$
f(n) = 2f(n-1) + f(n-2).
$$
with
$$
f(0) = 1 \quad\text{and}\quad f(1) = 3.
$$
For $g$: If the first digit is a 0 or a 1, then the remaining part is an arbitrary legitimate sequence of length $n-1$.
If the first digit is a 2, then the remaining part must have the form
$$
\underbrace{1\ldots 1}_{n-1\text{ times}}
$$
or
$$
\underbrace{1\ldots 1}_{i\text{ times}}0 s
$$
where $i\in\{0,\ldots,n-2\}$ and $s$ is a legitimate sequence of length $n-i-2$.
So
$$
g(n) = 2g(n-1) + 1 + \sum_{i=0}^{n-2} g(n-2-i)
= 2g(n-1) + \sum_{i=0}^{n-2} g(i) + 1.
$$
with
$$
g(0) = 1.
$$
A: As requested here is an alternative solution for $g$:
We call the sequences with the requested property g-sequences.
Furthermore, we call a sequence X-sequence if adding a symbol 2 in the end yields a g-sequence. Obviously, any X-sequence is a g-sequence too.
Let $X(n)$ be the number of X-sequences of length $n$.
If the last symbol of a g-sequence is 0 or 1, the remaining part is an arbitrary g-sequence.
If the last symbol is 2, the remaining part is an arbitrary X-sequence.
So
$$g(n) = 2g(n-1) + X(n-1).$$
An X-sequence cannot end on the symbol 2.
If the last symbol of a X-sequence is 0, then the remaining part is an arbitrary g-sequence. (But not necessarily a X-sequence, look for example at the sequence 20.)
If the last symbol of a X-sequence is 1, then the remaining part is an arbitrary X-sequence. So
$$X(n) = g(n-1) + X(n-1).$$
Iterated replacement of the expressions $X(i)$ in the recursion for $g(n)$ yields the recursion formula of the other answer (involving the summation).
