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?

  • $\begingroup$ Can you define what $a_n$ is? $\endgroup$ – Clement C. Oct 10 '14 at 14:32
  • $\begingroup$ I am suppose to find a recurrence relation for $a_n$ so I can calculate every $n$ with this formula $\endgroup$ – drleifz Oct 10 '14 at 14:34
  • $\begingroup$ Yes, but what is it supposed to represent? Number of tiles? Of light-color tiles? Half of the problem statement is missing. $\endgroup$ – Clement C. Oct 10 '14 at 14:36
  • $\begingroup$ It is suppose to represent how many valid pavements can I do with $n$ many tiles $\endgroup$ – drleifz Oct 10 '14 at 14:37
  • $\begingroup$ @drleifz could you edit your question and state that in the question itself? $\endgroup$ – Jemmy Oct 10 '14 at 14:39

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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