1. (16 points total 2 points each) In each situation, write a recurrence relation, including base case(s), that describes the recursive structure of the problem. Briefly explain how you obtain your recurrence. You do not need to solve for the closed-form formula. Note: For parts (g) and (h) of this problem, to "tile a rectangle" is to cover it with tiles so that no tiles overlap, no tiles are hanging off the edge of the rectangle, and every space on the rectangle is covered by some tile. (g.) Let T(n) be the number of ways to tile a 1 x n rectangle with 1 x 1 square tiles that are either rod or blue, and I 2 domino tiles that are green, white, or yellow. Write a recurrence for T(n). (h) Let L(n) be the number of ways to tile a 2 n rectangle with L-shaped tiles of area 3 (trominocs). Write a recurrence for L(n). 2. (5 points) At a Phi Beta Kappa party with n people, everyone high-fives once with everybody else. Let H(n) be the total number of high-fives among the n people. (a.) Write a recurrence for H(n). (b.) Use the guess-and-check method to obtain a closed-form formula for H(n). That is, first guess a formula for H(n) and use induction to prove that your guess is correct. 1. (16 points total 2 points each) In each situation, write a recurrence relation, including base case(s), that describes the recursive structure of the problem. Briefly explain how you obtain your recurrence. You do not need to solve for the closed-form formula. Note: For parts (g) and (h) of this problem, to "tile a rectangle" is to cover it with tiles so that no tiles overlap, no tiles are hanging off the edge of the rectangle, and every space on the rectangle is covered by some tile. (g.) Let T(n) be the number of ways to tile a 1 x n rectangle with 1 x 1 square tiles that are either rod or blue, and I 2 domino tiles that are green, white, or yellow. Write a recurrence for T(n). (h) Let L(n) be the number of ways to tile a 2 n rectangle with L-shaped tiles of area 3 (trominocs). Write a recurrence for L(n). 2. (5 points) At a Phi Beta Kappa party with n people, everyone high-fives once with everybody else. Let H(n) be the total number of high-fives among the n people. (a.) Write a recurrence for H(n). (b.) Use the guess-and-check method to obtain a closed-form formula for H(n). That is, first guess a formula for H(n) and use induction to prove that your guess is correct