4. 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,6, (k+2)r + m, k +1) recursive case for n > 1. and: =m =T h(0,m,r, k) = base case 0, h(1, m,r, k) = base case 1, and h(n, m, r, k) = (n +k).h(n 1, m, r,k)+h(n 2, m,r, k)? 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 f(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,6, (k+2)r + m, k +1) holds