Let $T(n)$ denote the number of ways to color $'n'$ houses such that house immediately right to the red or the blue is green.
Consider the first house in the row. It can be either red, green or blue. (Dividing the problem into three cases).
Suppose the first house is painted green so for next house, we don't have any condition, It can be painted by using any of the colors,$(R, G \text{ or } B).$
Hence If the first house is green we can paint the rest of the houses in $T(n-1)$ ways.
Suppose the first house is red, then for the next house we don't have any choice, it must be green.
So, if the first house is red, the number of ways of painting the rest of the houses is $T(n-2).$ (excluding the second house).
Same applies if the first house is blue, in that case also in $T(n-2)$ ways we can paint the houses.
Summing up all the mutually exclusive cases,
- $T(n) = T(n-1) + T(n-2) + T(n-2).$
- $T(n) = T(n-1) + 2T(n-2).$
Now consider the base case:
If we have $1$ house to paint it can be either red, green or blue. So $T(1)=3.$
For $2$ houses, $GR, GB, GG, BG \ \text{ (or) }\ RG$ are the $5$ possible ways. So, $T(2)=5.$$$\begin{array}{|l|l|}\hline T(1) & T(2) & T(3) & T(4) & T(5) & T(6) & T(7) & T(8) & T(9) & T(10) \\\hline 3 & 5 & 11 & 21 & 43 & 85 & 171 & 341 & 683 & 1365 \\\hline\end{array}$$
Option $(C).$