Combinatorics: Finding recurrence relation

[Askhwhelp]

Find the number of ways to arrange three types of flags on an n foot flag pole: red flags (1 foot high), white flags (1 foot high), blue flags (3 feet high)

Find a recurrence relation for this number with one condition that there cannot be three 1 foot flags in a row (regardless of their color).

R= Red, W=White, B=Blue

a_1 = 2, R, W
a_2 = 4, RW, WR, WW, RR
a_3 = 1, B
a_4 = 4, B(a_1), W(a_3), R(a_3)
a_5 = 12, B(a_2), W(a_4), R(a_4)
a_6 = 21, B(a_3), W(a_5-2(a_3)), R(a_5-2(a_3))
a_7 = 30, B(a_4), W(a_6-2(a_4)), R(a_6-2(a_4))
a_8 = 24, B(a_5), W(a_7-2(a_5)), R(a_7-2(a_5))
a_9 = -number,B(a_6), W(a_8-2(a_6)), R(a_8-2(a_6))
Since there is a negative number, I do not think this is right...could anyone point out what I did wrong?

 

[Office_Shredder]

R(a_5-2(a_3))

doesn't look like the right way to count the number of flags that are six high and have a red on top. For starters, you are claiming there are ten such flags, and really you can only do (I think)

R
R/W
B
R/W

or
R
B
R/W
R/W

of which there are only eight such flags. Instead of trying to subtract away flags that you originally constructed that are actually illegal, just think about if you start with a R on top, what are the only possible chains you can have before you reach a B? Once you know that you have placed B everything underneath it is counted using your recurrence relation.

 

[haruspex]

I approach this sort of problem by creating several related recurrence terms. You can have the total number of height n, the number of height n with at most one 1-foot flag on top, and the number that have a 3-foot flag on top. Then you can construct three recurrence relations that connect them.

 

[Askhwhelp]

Let a_n be the arrangement of flags at n feet. Just figure it out...is it a_n = a_(n-3)+2*a_(n-4)+4*a_(n-5). The initial value is a_2= 1, a_2 = 4, a_3 = 1, a_4 = 4,a_5 = 12

 

[haruspex]

Let a_n be the arrangement of flags at n feet. Just figure it out...is it a_n = a_(n-3)+2*a_(n-4)+4*a_(n-5). The initial value is a_2= 1, a_2 = 4, a_3 = 1, a_4 = 4,a_5 = 12

I get the same recurrence relation.