In this question we study the recursively defined functions f, g and h given by the following defining equations

f(0) = −1 base case 0,

f(1) = 0 base case 1, and

f(n) = n · f(n − 1) + f(n − 2)^2 recursive case for n ≥ 2.

and

g(0, m, r, k) = m base case 0, and

g(n, m, r, k) = g(n − 1, r,(k + 2)r + m^2 , k + 1) recursive case for n ≥ 1.

and:

h(0, m, r, k) = m base case 0,

h(1, m, r, k) = r base case 1, and

h(n, m, r, k) = (n + k) · h(n − 1, m, r, k) + h(n − 2, m, r, k)^2 recursive case for n ≥ 2.

Note in the following questions computations of the values of recursive functions should be laid out as a sequence of equations, as we have done in the lectures. Each line of that sequence should involve the application of a single defining equation of that function along with any resulting numerical evaluations.

In computations of this kind, an expansion step (or just a step) is an application of one of the defining equations of a recursive function to a single instance of that function in an expression. a. Compute the value of f(5). Write out your computation in full.

b. Compute the value of g(5, −1, 0, 0). Write out your computation in full.

c. How many expansion steps are required to evaluate the expression g(n, m, r, k) for some fixed natural numbers n, m, r and k? Explain your answer.  

d. Write down a recursive definition for the function c which maps each natural number n to the number of steps c(n) that it takes to evaluate the expression f(n). Explain your answer.

Hint: to work out how to define c start by performing the kind of “bullet point” analysis we used in the lectures to show that it takes n + 1 expansion steps to evaluate n!. You can then give that analysis as your explanation of how you came up with your defining equations for c.

e. Use strong induction to prove that the function c that you defined in part 4d does indeed have the stated property. That is you should prove that for all natural numbers n it takes c(n) expansion steps to completely evaluate the expression g(n).

f. Use strong induction to prove that for all n ≥ 1 and all natural numbers m, r and k the equation h(n, m, r, k) = h(n − 1, r,(k + 2)r + m^2 , k + 1) holds.

g. Explain why the result you proved in part 4f implies that the functions h and g are equal.

h. Explain why it is the case that for all natural numbers n we have that f(n) = h(n, −1, 0, 0) = g(n, −1, 0, 0).

i. A software engineer needs to evaluate expressions of the form f(n) in her code but, given the analysis above, she opts to use expressions of the form g(n, −1, 0, 0) instead. Explain why it is OK to do that and why you think this engineer might have made that choice.