Flag Stacking Problem

Question

I am confused on part b). I am pretty sure part a) is correct. If someone could explain/show where I am going wrong, it would be much appreciated.

Part a) : Find a recurrence relation for the number of ways to arrange three types of flags on a flagpole n feet high: red flags (1 foot high), gold flags (1 foot high), and green flags (2 feet high).

My solution to this was $A_n = 2A_{n-1} + A_{n-2}$ with $A_0 = 1, A_1 = 2$

Part b) Repeat part (a) with the condition of no red above gold above green (in a row).

My Solution:
$A_0 = 1, A_1 = 2, A_2 = 5$
My thinking is it would be the same as part a), but when last flag in sequence is red, subtract 1 for the scenario when it matches the forbidden subsequence.
So, my solution would be $A_n = (A_{n-1} - 1) + A_{n-1} + A_{n-2}$ with $A_0 = 1, A_1 = 2$

Answer 1

Personally in (a) I would say $A_n=2A_{n-1}+A_{n-2}$ starting with $A_0=1$ and $A_n=0$ for $n<0$. This gives the same result as yours: $1,2,5,12,29,70,169,\ldots$.

Then for (b) I would say $A_n=2A_{n-1}+A_{n-2}-A_{n-4}$ starting with $A_0=1$ and $A_n=0$ for $n<0$. This gives: $1,2,5,12,28,66,155,\ldots$