Question

In: Computer Science

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

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

Solutions

Expert Solution

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


Related Solutions

In this question we study the recursively defined functions f, g and h given by the...
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...
If f and g are both differentiable functions. If h = f g, then h'(2) is: ___________________
  If f and g are both differentiable functions. If h = f g, then h'(2) is: ___________________ Given the function: y=sin(4x)+e^-3x and dx/dt = 3 when x=0. Then dy/dt = ________________ when x=0. Let f(x) = ln (√x). The value of c in the interval (1,e) for which f(x) satisfies the Mean Value Theorem (i.e f'(c)= f(e)-f(1) / e-1 ) is: _________________________ Suppose f(x) is a piecewise function: f(x) = 3x^2 -11x-4, if x ≤ 4 and f(x) =...
For the given functions f and​ g, complete parts​ (a)-(h). For parts​ (a)-(d), also find the...
For the given functions f and​ g, complete parts​ (a)-(h). For parts​ (a)-(d), also find the domain. f left parenthesis x right parenthesis equals StartFraction 7 x plus 9 Over 9 x minus 7 EndFractionf(x)=7x+99x−7​; g left parenthesis x right parenthesis equals StartFraction 9 x Over 9 x minus 7 EndFractiong(x)=9x9x−7​(a) Find ​(fplus+​g)(x). ​(fplus+​g)(x)equals=nothing ​(Simplify your​ answer.)What is the domain of fplus+​g? Select the correct choice below​ and, if​ necessary, fill in the answer box to complete your choice. A.The...
Let f : N → N and g : N → N be the functions defined...
Let f : N → N and g : N → N be the functions defined as ∀k ∈ N f(k) = 2k and g(k) = (k/2 if k is even, (k + 1) /2 if k is odd). (1) Are the functions f and g injective? surjective? bijective? Justify your answers. (2) Give the expressions of the functions g ◦ f and f ◦ g? (3) Are the functions g ◦ f and f ◦ g injective? surjective? bijective?...
Let f : X → Y and g : Y → Z be functions. We can...
Let f : X → Y and g : Y → Z be functions. We can define the composition of f and g to be the function g◦ f : X → Z for which the image of each x ∈ X is g(f(x)). That is, plug x into f, then plug theresultinto g (justlikecompositioninalgebraandcalculus). (a) If f and g arebothinjective,must g◦ f beinjective? Explain. (b) If f and g arebothsurjective,must g◦ f besurjective? Explain. (c) Suppose g◦ f isinjective....
For countable set G, H = {f : N → G : f is injective} where...
For countable set G, H = {f : N → G : f is injective} where N is the natural numbers. What is the cardinality of H. Prove it.
Only need assistance on question F, G, and H!!! For this problem use the “plastic hardness”...
Only need assistance on question F, G, and H!!! For this problem use the “plastic hardness” data which can be found in Moodle PLASTIC.dat . The first column is the plastic hardness (Y ) and the second column is the elapse time (X) 199.0 16.0 205.0 16.0 196.0 16.0 200.0 16.0 218.0 24.0 220.0 24.0 215.0 24.0 223.0 24.0 237.0 32.0 234.0 32.0 235.0 32.0 230.0 32.0 250.0 40.0 248.0 40.0 253.0 40.0 246.0 40.0 (a) Plot the a scatter...
Given, op: (λ(n) (λ(f) (λ(x) (((n (λ(g) (λ(h) (h (g f))))) (λ(u) x)) (λ(u) u))))) zero:...
Given, op: (λ(n) (λ(f) (λ(x) (((n (λ(g) (λ(h) (h (g f))))) (λ(u) x)) (λ(u) u))))) zero: (λ(f) (λ(x) x)) one: (λ(f) (λ(x) (f x))) two: (λ(f) (λ(x) (f (f x)))) three: (λ(f) (λ(x) (f (f (f x))))) i. (4 pt) What is the result of (op one)? ii. (4 pt) What is the result of (op two)? iii. (4 pt)What is the result of (op three)? iv. (3 pt) What computation does op perform?
Q3.15You have been given the following return data on three assets: F, G and H and...
Q3.15You have been given the following return data on three assets: F, G and H and the two portfolios – over the period 2013 to 2016: Year Asset F Asset G Asset H Portfolio FG Portfolio FH 2013 16 17 14 16.5 15 2014 17 16 15 16.5 16 2015 18 15 16 16.5 17 2016 19 14 17 16.5 18 Using these assets, you have isolated three investment alternatives: 100% of Asset F   50% of Asset F and 50%...
Let⇀F and⇀G be vector fields defined on R3 whose component functions have continuous partial derivatives. Furthermore,...
Let⇀F and⇀G be vector fields defined on R3 whose component functions have continuous partial derivatives. Furthermore, assume that ⇀∇×⇀F=⇀∇×⇀G.Show that there is a scalar function f such that ⇀G=⇀F+⇀∇f.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT