I have the following problem: “A flag is to be made with n horizontal stripes by using the colours yellow, blue, green and red in such a way that none of the adjacent stripes have same colour, and neither do the first and last stripe. Find the amount of flags that can be made by following the restrictions.”
I solved a similar problem in which the only restriction that I had was that none of the adjacent stripes have the same colour. In order to do it I consider the case in which the nth stripe was red as so the number of flags ($a_n$) were $3a_{n-2}$ Since the other cases are basically the same, I got that: $a_n=12a_{n-2}$ And so by solving the recurrence I got the answer. However, I don’t know how to apply the second restriction that is given in the exercise.
Before the first/last restriction, the recurrence should be $a_n=3a_{n-1}$ because given any flag with $n-1$ stripes you have $3$ choices to make the $n^{th}$ stripe. The four choices for the first stripe give $a_1=4$ and the general solution is $a_n=4\cdot 3^{n-1}$
Let $b_n$ be the number of flags with $n$ stripes, no neighboring stripes the same, and the same first and last colors. Let $c_n$ be the number of flags with $n$ stripes, no neighboring stripes the same, and the first and last stripes different. We can write coupled recurrences $$a_n=b_n+c_n\\b_n=c_{n-1}\\c_n=3b_{n-1}+2c_{n-1}$$ because a c flag can be extended to a b flag in one way, while a b flag can be extended to a c flag in three ways and a c flag can be extended to a c flag in two ways. This makes the recurrence $$c_n=2c_{n-1}+3c_{n-2}\\c_n=p3^n+q(-1)^n$$ For initial conditions we have $c_2=12, c_3=4\cdot 3^2-12=24$ giving $p=1,q=3$ and $$c_n=3^n+3(-1)^n$$