Thread: Please Help! Recurrence Problem!

2. Consider the following situation: you need to tile a walkway with tiles of three colors (red, green, and black). The one rule that must be obeyed is that you may never have consecutive red tiles. Let an represent the number of different patterns for an n-tile walkway.

A. Find a recurrence relation (don’t forget initial conditions) for the sequence an. Be certain to explain why it applies.

B. Use the generating functions method developed in class to find an
explicit formula for the a sequence.

can anyone help? I have no idea how to even start.

This is what came in y mind.

Consider an as sequence of n tiles.

There can be two case. nth tile is red or nth tile is not red.

Case I nth tile is red.
In that can for an+1 there can be either green tile or black tile in n+1 position. there cant be erd tile (as no consecutive red tile).
So an+1 = an +2 --------- eq1

Now n+1 tile is not red. so n+2 tile can be either of tree color.
so an+2 = an+1 + 3 ---------eq2

adding eq1 and eq2
an+2 = an +5



Case II
nth tile is not red
so n+1 tile can be either of 3.
so an+1 = an +3 ---eq3

And the case where n+1 tile is red,
an+2 = an+1 +2 ------eq4

adding eq3 and eq4

an+2 = an+5

----------------------------------------------------------

So in both the case we are getting recuursive relation as

an+2 = an+5 Answer.


I need to think more over this.
let m know if you feel answer is wrong. We can discuss the problem further.