1
$\begingroup$

This is homework, please only provide hints.

I've been given a problem: consider a 1-by-n chessboard. Coloring each square with one of two colors, red or blue. Let $a_n$ be the number of colorings in which no two squares that are red are adjacent.

So, I started off with two cases: 1) possible colorings where the last square is blue. 2) colorings where the last square is red.

length(n = 1) (last square blue): $\left \{ B\right \}$ (last square red): $\left \{ R\right \}$ which leaves us with 2 possible choices

length(n = 2) blue: $\left \{ RB\right \}$ $\left \{ BB \right \}$ red: $\left \{ BR \right \}$ which leaves us with 3 possible choices

etc..

At this point, I'm basically stuck. I noticed these numbers begin to look like the Fibonacci sequence. So obviously my solution is (I confirmed in the book):

$$a_n = a_{n-1} + a_{n-2}$$

My issue is, I only know that because I recognized the sequence. If this was a random sequence, how should I set it up to determine the relation?

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

HINT: You can get a legal $1\times n$ coloring by adding $B$ to any legal $1\times(n-1)$ coloring, or by adding $BR$ to any legal $1\times(n-2)$ coloring. Is there any other way to get one?

$\endgroup$
2
  • $\begingroup$ couldn't you potentially get a legal coloring by adding an R or RB respectively? Do I not need to take that in to count here? $\endgroup$
    – intervade
    Feb 10, 2013 at 18:12
  • $\begingroup$ @intervade: You could, but you could also get an illegal one. The point is that my two cases (a) give you every legal coloring of the $1\times n$ board, (b) never give you an illegal coloring, and (c) don’t overlap (i.e., no coloring is in both cases). Thus, $a_n$ is the sum of the numbers in the two cases, and that turns out to be exactly what you want. $\endgroup$
    – Brian M. Scott
    Feb 10, 2013 at 22:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .