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.