# finding recurrence relations

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?

-

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?
@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