Consider the following combinatorial identity.

((k 2) 2) = 3(k+1 4)

a) Prove the identity by algebraic manipulation.

b) Give a combinatorial proof. (Hint: The lefthand side counts the number of combinations of two combinations of k items taken two at a time. Consider the following algorithm for generating such an item: Take the k items and add a k+1st element DUP. Each pair of combinations of k items taken two at a time can be obtained by choosing 4 items from the expanded set of k + 1 elements. If none of those four is DUP, there are 3 possible pairs of combinations of two items (why?). If one of those items is DUP, any one of the three other items can be duplicated to get a total of 4 elements. In that case, how many possible pairs of combinations of two items are there?