Consider the following puzzle. There is a row of n chairs and two types of people: M for mathematicians and P for physician. You want to assign one person to each seat but you can never seat two mathematicians together or they will start talking about mathematics and everyone else in the room will get bored. For example, if n = 3, the following are some valid seatings: PPP, MPM, and PPM. However, the following is an invalid seating: MMP. In this problem, your goal is as follows. Let f(n) be the number of valid seatings when there are n chairs in a row. Write and solve a recurrence relation for f(n). Please show your work