4 Let hn be the number of ways to color the squares of an 1

4. Let hn be the number of ways to color the squares of an 1 × n chessboard with red and blue so that no two red squares are adjacent. Find a recurrence relation for hn.

Solution

The first square of the 1*n board must either be red or blue. In case of blue, the remaining n-1 squares can be colored by either red or blue. It gives one choice as h_n-1

On other way if first square is red, the next one must be blue. The remaining n-2 squares can be colored in such a way that no adjucent red is there. So only one choice as h_n-2

So h_n = h_n-1 + h_n-2