Explore BrainMass

Recurrence Relation: coloring 1xN chessboard with two colors

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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

Solution Preview

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 Summary

Solution derives the recurrence relation explaining each step briefly.