A The graduate-student job problem made worse. Consider the following depressing scenario: Every year, each professor of computer science graduates one new graduate student who holds a postdoc for one year and then goes on to become a professor the following year. To compound the miseries of newly graduating students, in year n ≥ 2, there are 2^{n−2} physicists who change careers to become computer science professors without going to graduate school. Let f(n) denote the number of computer science professors after n years. Assume f(0) = 0 and f(1) = 1. It follows that f(2) = 2: in year 2, there are two CS professors, namely the one CS professor from year 1 and the one physicist transfer (there is also one postdoc who graduated in year 1 and will be professor in year 3).

• Compute f(3), f(4), and f(5).

• Set up a recurrence relation obeyed by f(n).

• Solve your recurrence to find a closed form for f(n).

B Using genetic engineering, farmers have recently created a new type of fruit. Once planted, a single fruit will produce a tree which will produce more fruit at the following rate. After one year, the tree produces one fruit, after two years, the tree will produce two fruits, after three years, it will produce three fruits, etc. In general, a tree that has been planted for n years will produce n fruits. Upon harvest, the farmer immediately plants all available fruits. Suppose the farmer starts with one fruit in year 1, which he plants. Let f(i) be the number of fruits the farmer plants in year i.

• Write down the first few values of f(i).

• Write a recurrence relation for computing f(i).

• Solve the recurrence to obtain a closed-form expression for f(i).