Problem B: Let an be the number of of ways to lay out a walkway of n tiles, with slate tiles if the tiles are red, green, black or grey, so that no two red tiles are adjacent. (a). Write a recurrence for an- (b). Write a complete set of initial conditions. (c). Calculate a3 using your recursion from (a) and initial conditions from (b). (d). Now assume that three adjacent red tiles are not allowed (but two adjacent reds are allowed). Write a recurrence for an. (e). Write a complete set of initial conditions for your recurrence of part (d). Divide and Conquer Solutions Solutions to the recurrence an = can/k + f(n) are given by C f (n) an C = 1 d d [logk n] + A c = k d An - K-I dn Anlosk C+ K-C n C = k dn dn([logk n] + A)