On a certain block, there are five houses in a line, which are to be painted red or...
Check the final answer first, then review the worked steps.
Check the final answer first, then review the worked steps.
a_1 = 2, a_2 = 3, a_3 = 5, a_4 = 8, a_5 = 13
Let $a_n$ be the number of ways to paint $n$ houses. If the $n$-th house is green, there are $a_{n-1}$ ways. If the $n$-th house is red, the $(n-1)$-th must be green, leaving $a_{n-2}$ ways. Thus $a_n = a_{n-1} + a_{n-2}$, which is the Fibonacci sequence. For $n=5$, $a_1=2$ (R, G), $a_2=3$ (RG, GR, GG), $a_3=5$, $a_4=8$, $a_5=13$.