Find a recurrence relation for the number of ternary strings of length n that after 1 there is no 0 nor 2

Question

Find a recurrence relation for the number of ternary strings of length n that after 1 there is no 0 nor 2.

Don't know how to approach these kinds of problems.

Answer 1

HINT: Let $S_n$ be the set of such strings of length $n$. Notice that if $\sigma=s_1\ldots s_n\in S_n$, and there is a $k$ such that $s_k=1$, then $s_i=1$ for $k\le i\le n$. That is, if a string in $S_n$ has a $1$, every element after that $1$ must also be a $1$.

• How many ternary strings of length $n$ have no $1$s?
• More generally, if $0\le k\le n$, how many ternary strings of length $n$ end in exactly $k$ $1$s and have only $0$s and $2$s before those $1$s?

Every member of $S_n$ must be of the kind described in the last bullet point.