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) 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) Let C(n) be the number of 1 x 1 cells in an n x n grid. Write a recurrence for C(n).
(c) 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 . Write a recurrence for A{n).
(d) Let B(n) be the number of length n binary strings that have no three consecutive O's. Write a recurrence for B(n).
(e) 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).