Find a recurrence relation for $a_n$, the number of sequences of red, white and yellow flags along an $n$-foot high flagpole if red flags are 1, white flags are 2 and yellow flags are 3 feet tall, and no two red flags can be side-by-side.
Why is the answer $a_n=a_{n-2}+2a_{n-3}+a_{n-4}$? How does that incorporate the last restriction?
Hint: let $b_n$ be the number of sequences of length $n$ that do not have red on top and $c_n$ be the number of sequences of length $n$ that have red on top. $a_n=b_n+c_n$. Write coupled recurrences for $b_n$ and $c_n$. The definition of $b_n,c_n$ lets you ensure the restriction by writing the recurrences properly.
Use $w$ as variable for admissible words over the alphabet $\{1,2,3\}$. Then each $w$ is of one of the forms $2w'$, $3w'$, $12w'$, $13w'$. From this one immediately deduces $$a_n=a_{n-2}+a_{n-3}+a_{n-3}+a_{n-4}=a_{n-2}+2a_{n-3}+a_{n-4}\qquad (n\geq4)\ .$$
