Recurrence Relation of n-digit quaternary?

Question

Determine the n-digit quaternary (0,1,2,3) sequences in which there is never a 3 anywhere to the right of a zero.

So I know that the answer is $a_{n+1}$ = $3a_{n}$ + $3^n$. I understand why it is $3a_{n}$, because if at the $n+1$ the sequence ends with a 1,2 or 3, then at $a_{n}$ I can have have the choice of 0,1,2, or 3. I just don't understand why I'm suddenly using counting for the $3^n$. Also, when do we use counting when it comes to recurrence relations.

Thanks for any help. Sorry if what I'm asking is a bit confusing.

Answer 1

Hint. See if you can fill in the dots: an $n+1$-digit sequence of the type you want consists of

• $0$ followed by . . . . . . ; or
• $1,2$ or $3$ followed by . . . . . .