6. During an early morning drive to work, Simon encountered $n$ sets of traffic lights, each set being red, amber or green as he approached it. He noticed that consecutive lights were never the same colour.
Given that he saw at least two red lights, find a simplified expression, in terms of $n$, for the number of possible sequences of colours Simon could have seen.
Solution
We will find three separate expressions, each relating to sequences which satisfy the condition that consecutive lights were never the same colour:
(i) $T_{n}=$ Total number of possible sequences of length $n$.
Consider the first colour encountered, it can be red, amber or green. This gives three choices for the first colour.
Next consider the second colour encountered, this must not be the same as the first colour but could be either of the other two colours. This gives two choices for the second colour.
Considering subsequent colours is much the same as considering the second, the next colour in the sequence cannot be the same as the previous colour but can be one of the other two.
This means that for the first colour there are three choices and for each colour after the first there are two choices and so $T_{n}=3 \times 2^{n-1}$.
(ii) $R_{0_{n}}=$ Number of possible sequences, of length $n$, which contain zero red lights.
Consider the first colour encountered, it cannot be red so must be amber or green. This gives two choices for the first colour.
If the first colour is amber, the second must be green, the third amber and so on. If the first colour is green, the second must be amber, the third green and so on.
This means that $R_{0_{n}}=2$, which is independent of $n$ and thus we will refer to it as $R_{0}$.
(iii) $R_{1_{n}}=$ Number of possible sequences, of length $n$, which contain exactly one red light.
If red appears as the first or last colour encountered then we must have a sub-sequence of length $(n-1)$ which contains no red lights. There are $R_{0}=2$ of these in each case, so $2 \times R_{0}=4$ possible sequences.
If red appears elsewhere, then either side of it we must have sub-sequences which contain no red lights. This means for each possible position of the colour red we have $R_{0}$ choices for each of the two sub-sequences, and so $R_{0} \times R_{0}=4$ possible sequences of length $n$. As there are $n-2$ positions (which are not first or last) this gives $4(n-2)$ possible sequences.
This means that $R_{1_{n}}=4+4(n-2)=4 n-4$.

Finally, we have that the number of possible sequences containing at least two red lights is $T_{n}-R_{0}-R_{1_{n}}=3 \times 2^{n-1}-2-(4 n-4)$ which simplifies to $3 \times 2^{n-1}-4 n+2$.