3. Suppose there are n chairs in a row. We want to compute the number of ways to put 2 students into seats so that they are not next to each other. Assume that students are interchangeable: e.g., if n = 3, the solution should be 1, because the only way to accomplish this is to use the first and last chairs. For both parts to this problem, you must explain why your answer is correct: it is not sufficient to compute a few values directly and look for a pattern. (a) Write a recurrence relation describing the number of ways to put the 2 students into seats so that they are not next to each other. (b) Repeat part a, but now suppose the chairs are in a circle (hint: it might help if you label the chairs 1, ... n, even though they are in a circle without a 'start' or 'end')