Finding the recurrence relation.

Question

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.

Answer 1

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).

Answer 2

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. $$