8. [9 marks] Let an denote the number of subsets of the set {1, 2, ..., n} which do not contain two consecutive integers. Develop a recurrence relation for an. Explain your work in developing the recurrence relation. State a, and az. Suggestion: think of whether the number n is in the set or not. (To avoid writing set not containing two consecutive integers several times, you may refer to such a set as good.) 9. [8 marks] Use the Pigeonhole Principle to solve the following problem. During the last 44 days of his final year of university, Nachiket sends out at least one resume per day, but no more than 62 resumes in total. Use the Pigeonhole Principle to show that there is a consecutive period of days during which he sent out exactly 25 resumes. What are the pigeonholes and how many of them are there? What are the pigeons and how many of them are there? State the Pigeonhole Principle and explain how it gives the result. 10.[4 marks] (a) For what values of x,y and z does the Boolean function f(x, y, z) = x(y + 2) equal 1. (b) Represent f by using a hypercube. 11.[4 marks] Determine whether or not the following graph is planar. If it is planar, give a planar representation. If it is not planar, give convincing evidence that it is not planar. 8. [9 marks] Let an denote the number of subsets of the set {1, 2, ..., n} which do not contain two consecutive integers. Develop a recurrence relation for an. Explain your work in developing the recurrence relation. State a, and az. Suggestion: think of whether the number n is in the set or not. (To avoid writing set not containing two consecutive integers several times, you may refer to such a set as good.) 9. [8 marks] Use the Pigeonhole Principle to solve the following problem. During the last 44 days of his final year of university, Nachiket sends out at least one resume per day, but no more than 62 resumes in total. Use the Pigeonhole Principle to show that there is a consecutive period of days during which he sent out exactly 25 resumes. What are the pigeonholes and how many of them are there? What are the pigeons and how many of them are there? State the Pigeonhole Principle and explain how it gives the result. 10.[4 marks] (a) For what values of x,y and z does the Boolean function f(x, y, z) = x(y + 2) equal 1. (b) Represent f by using a hypercube. 11.[4 marks] Determine whether or not the following graph is planar. If it is planar, give a planar representation. If it is not planar, give convincing evidence that it is not planar