Recurrence relation for $n$ digit numbers not containing '$20$'

Question

How many n digits base $3$ numbers do exist such that they never contain pattern '$20$'? (first find a recurrence relation)

Answer 1

Hint: Let $a(n)$ be the sequence we are looking for. Let $b(n) , c(n), d(n)$ be the number of ternary strings (and so they can start with 0) which do not contain the pattern '20', and start with 0, 1 and 2 respectively.

What equations can you get?

Claim: $a(n) = b(n) + c(n) + d(n)$.
Claim: $b(n) = c(n) = b(n-1) + c(n-1) + d(n-1)$.
Claim: $d(n) = c(n-1) + d(n-1)$.

Can you take it from here?

$b(n) = a(n-1)$, $d(n) = a(n-1) - b(n-1) = a(n-1) - a(n-2)$. Hence ...