Let T(n) is the number of ways to color 'n' houses.
Task: To find T(10) for 10 houses
1. When one house is painted: no of ways are G or B or R, T(1) -> 3 ways
2. When two houses are painted: no of ways are RG, BG, GB, GG, GR T(2) -> 5 ways
3. When three houses are painted: no of ways are GGB, GGR, GGG, GRG, GBG, RGR, RGB, RGG, BGB, BGR, BGG T(3) -> 11 ways.
so, from the above pattern is 3, 5, 11...(till 10th house)
if you look at the pattern you will find it as a famous pattern named Jacobsthal Number
that is, 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, ……
so, starting from 3 as the first house and move right till 10th (value) you will find the answer 1365.
therefore by the pattern, we can find the ways to paint 10 houses ie T(10) ways
Answer : T(10) = 1365 ways