Finding recurrence relation on a problem

Question

I need a little bit help finding a recurrence relation. So it goes like this:

"A one-sided pavement is being made with tiles that come in 5 different colors. There are 3 light colors (light-yellow, light-green and light-red) and then there are 2 dark colors (dark-red and dark-blue). It is required that the total of tiles in light colors are an odd-number.

a) Find $a_1$ og $a_2$ b) Put forth a recurrence relation along with initial conditions for $a_n$. c) Use the recurrence relation to calculate $a_5$

I am really stranded and don't know to do this. I have been trying to look at similar examples but can't seem to find this out. How many valid pavement can I make with the requirement met?

Answer 1

HINT: If you use only one tile, it must be a light-colored tile, so that you have an odd number of light-colored tiles; thus, $a_1=3$. If you use two tiles, exactly one must be light-colored, and you can arrange your two tiles in either order, so $a_2=\ldots\;$?

Now suppose that $n\ge 3$, and $T_1T_2\ldots T_n$ is an acceptable string of $n$ tiles, i.e., one with an odd number of light-colored tiles. Look at $T_n$, the last tile. If it’s dark-colored, then $T_1T_2\ldots T_{n-1}$ is an acceptable string of $n-1$ tiles. There are $a_{n-1}$ of those, and there are $2$ dark colors, so this accounts for $2a_{n-1}$ acceptable strings of $n$ tiles, all those that end in a dark tile. What if $T_n$ is a light-colored tile? Then $T_1T_2\ldots T_{n-1}$ is an unacceptable string of $n-1$ tiles.

• How many strings of $n-1$ tiles are there altogether? Subtract $a_{n-1}$ from that to get the number of unacceptable ones.
• How many possibilities are there for $T_n$ in this case?
• In terms of $a_{n-1}$ how many acceptable strings of $n$ tiles are there in which the last tile is light-colored?

If you’ve answered all of those correctly, you should be able to write down the desired recurrence. (The numbers $a_n$ increase quite rapidly with $n$, but it’s not hard to calculate $a_3$ and even $a_4$ directly to provide a check on the recurrence that you find.)