1. In each situation, write a recurrence relation, including base case(s), for the given function. Briefly explain in words why this recurrence describes the situation. You do not need to solve the recurrence (that is, get a closed-form formula) (a) (2 points) In a round-robin thumb-wrestling tournament with n people, everybody thumb-wrestles with everybody else. Let T(n) be the total number of thumb-wrestling matches taking place among the n people. Write a recurrence for T(n) (b) (2 points) Let C(n) be the nurnber of 1 l cells in an n n grid. Write a recurrence for C(n) (c) (2 points) A bunch of motorcycles and cars want to parallel park on a street. The street can fit n motorcycles, but cars take up three motorcycle spaces. Let A(n) be the number of arrangements of cars and motorcycles on a street that fits n motorcycles. For example, A(5) 4 because there are four ways to park vehicles on a street with five motorcycle spaces. If M stands for motorcycle, and C stands for car, then the four arrangements are: MMC, MCM, CMM, and MMMMM. Write a recurrence for A(n) Write a recurrence for B(n) runs. For example, 001110100000 has: (d) (2 points) Let B(n) be the number of length n binary strings that have no three consecutive O's (e) (2 points) Any binary string can be broken into contiguous chunks of the same character, called a run of Os of length 2 a run of 1s of length 3 a run of Os of length 1 o a run of 1s of length 1 o a run of Os of length 5 Let B(n) be the number of length n binary strings where each run of 1s has even length. Find a recurrence for B(n) (f) (2 points) Let S(n) be the number of subsets of {1,2,... , n^ having the following property: no two elements in the subset are consecutive integers. The empty set with no elements should be included in your count. Write a recurrence for S(n)