Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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?

share|improve this answer
    
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? –  intervade Feb 10 '13 at 18:12
    
@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. –  Brian M. Scott Feb 10 '13 at 22:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.