This is a problem from my textbook:
Call a ternary string good if it never contains a $2$ followed immediately by a $0$; otherwise, call it bad. Let $g(n)$ be the number of good strings of length $n$. Obviously $g(1)=3$, since all strings of length $1$ are good. Also, $g(2)=8$ since the only bad string of length $2$ is $(2,0)$. Now consider a value of $n$ larger than $2$. Write a recursive formula for $g(n)$.
The textbook provides the solution but I am confused about it. It says that if the last digit is a $0$, then there are $g(n-1)$ valid strings that can precede it, and of these $g(n-1)$, $g(n-2)$ end in a $2$. I'm struggling with the intuition of why there are $g(n-2)$ strings ending in a $2$. Sorry if this is an obvious question, I'm just really confused.
You can think of "ending at $2$" as a process of adding $2$ to the last of the original string whose length is $n-2$. Apparently during this process, no extra bad strings are gonna pop out.
Therefore, the number of good strings (with length $n-1$) ending in a $2$ should equal $g(n-2)$.