In: Computer Science
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.
search what
PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU