Question

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.

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.

Answer 1

Ans: