How Can You Paint 16 Seats in Consecutive Odd Red or Green Colors?

[anemone]

Here is this week's POTW:

-----

In how many ways can we paint 16 seats in a row, each red or green, in such a way that the number of consecutive seats painted in the same color is always odd?

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to Opalg for his correct solution:), which you can find below:

Spoiler

Let $C_n$ be the number of ways of painting a row of $n$ seats according to those rules.

Notice that $C_1 = C_2 = 2$. (A single seat can be either red or green. A row of two seats can be either 1 red followed by 1 green, or 1 green followed by 1 red.)

Now think about a row of $n$ seats, divided into batches consisting of an odd number of consecutive seats of the same colour. There are two cases: the first seat in the row is either in a batch consisting of just that single seat, or it is in a batch of at least three seats.

Case 1 (a batch consisting of just one seat): There are then $n-1$ remaining seats, with $C_{n-1}$ ways of colouring them. In each case, the first seat will have to have the opposite colour to the first batch of the remaining seats. So that gives $C_{n-1}$ ways of colouring the row.

Case 2 (a batch consisting of at least three seats): Think of the first three seats as being a single unit (perhaps it is a three-seater bench?). Counting that bench as a single seat, we then have a total of $n-2$ units, and therefore $C_{n-2}$ ways of colouring them.

Putting the two cases together, you see that $C_n = C_{n-1} + C_{n-2}$. So the $C_n$s look exactly like the Fibonacci numbers $F_n$, except for the initial conditions $C_1 = C_2 = 2$ instead of $F_1 = F_2 = 1$. Therefore $C_n = 2F_n$, and $C_{16} = 2F_{16} = 2*987 = 1974.$