Consider a 1-by-n chessboard. Suppose we color each square of the chessboard with one of the two colors - red and blue. Let h(n) be the number of coloring in which no two squares that are colored red are adjacent. Find a recurrence relation that h(n) satisfies.© BrainMass Inc. brainmass.com March 21, 2019, 7:16 pm ad1c9bdddf
Since there are only two possibilities for coloring the first square - either blue or red.
If the first square is colored blue, then the number of ways to color n squares such that no two red squares are adjacent, will be ...
Solution derives the recurrence relation explaining each step briefly.