Recurrence relation for the number of ways to arrange $3$ different types of flags 
Find a recurrence relation for the number of ways to arrange red flags ($1$ ft. tall), yellow flags (1 ft. tall), and green flags ($2$ ft. tall) on an $n$ foot 
  tall pole s.t. there may not be three $1$-foot flags (red or gold) in a row.

I'm not sure if my answer is correct (no way of solution provided), could someone please let me know if my reasoning is right? 

Solution: Let G be green, R be red, Y be yellow. Define a "good" sequence to be one that does not violate the proposed constraint. 
Since there is no constraint on G, then G an be appended to any good $(n-1)$-sequence -- giving $a_{n-2}$ ways.
If an $n$-sequence ends in R or Y, then we can have:


*

*R or  Y in the $n$-th position and in the $(n-1)$-th position, which must be followed by G. This gives $4a_{n-4}$ ways

*R or Y in the  $n$-th position and G in the $(n-1)$-th position. This gives $2a_{n-3}$ ways. 


In all we have $a_n = a_{n-2} + 4a_{n-4} + 2a_{n-3}$ possible ways. 
 A: Just for kicks, let's see if we can get a concrete number out of this.
Your recurrence is $a_{n + 4} = a_{n + 2} + 2 a_{n + 1} + 4 a_n$. We also have $a_0 = 1$, $a_1 = 2$ (R or Y), $a_2 = 5$ (RR, RY, YR, YY, G), $a_3 = 4$ (RG, YG, GR, GY).
Define the ordinary generating function $A(z) = \sum_{n \ge 0} a_n z^n$. Using the respective properties:
$$
\frac{A(z) - 1 - 2 z - 5 z^2 - 4 z^3}{z^4}
  = \frac{A(z) - 1 - 2 z}{z^2} + 2 \frac{A(z) - 1}{z} + 4 A(z)
$$
This gives:
$$
A(z) = \frac{(1 + 2 z)^2}{1 - z^2 - 2 z^3 - 4 z^4}
$$
The roots of the denominator are all real, but extremely ugly looking expressions. Sorry.
A: Think of it this way:
Let $G_n$ be the number of ways to arrange flags on an $n$ foot pole assuming the last flag is a green flag. Let $Y_n$ be the equivalent for yellow/red flags. We're going to count the total, which is $T_n=G_n+Y_n$.
Now, a sequence ending in green can have any sequence two less prior to it. So
$$
G_n = T_{n-2}
$$
A sequence ending in red or yellow cannot have two such flags before it. So it must have a green either one (followed by a red or yellow) or two before it. And either red or yellow can be the final flag. That is,
$$
Y_n = 4G_{n-1}+2G_{n-2}
$$
So we have that
$$
T_n = T_{n-2}+4G_{n-1}+2G_{n-2}
$$
Substituting in our $G_n$ equation into $T_n$ gives
$$
T_n = T_{n-2} + 4T_{n-3}+2T_{n-4}
$$
where $T_0=1$, $T_1=2$, $T_2=5$, and $T_3=4$.
