Question

Which of the following proposed recursive definitions of a function on Z+ produce well-defined functions? If...

Which of the following proposed recursive definitions of a function on Z+ produce well-defined functions? If it is well-defined, provide a direct formula for F(n). Be sure to explain your answer, either why F is not well-defined, or why your direct formula is correct. (a) F(n) = 1 + F(bn/2c), for n ≥ 1, F(1) = 1 (b) F(n) = 2F(n−2) if n ≥ 3, F(2) = 1, F(1) = 0 (c) F(n) = 1 + F(n/2) if n is even and n ≥ 2, F(n) = F(3n−1) if n is odd and n ≥ 3, F(1) = 1.

Homework Answers

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Determine if each of the following recursive definition is a valid recursive definition of a function...
Determine if each of the following recursive definition is a valid recursive definition of a function f from a set of non-negative integers. If f is well defined, find a formula for f(n) where n is non-negative and prove that your formula is valid. f(0) = 1, f(n) = -f(n-1) + 1 for n ≥ 1 f(0) = 0, f(1) = 1, f(n) = 2f(n-1) +1 for n ≥ 1 f(0) =0, f(n) = 2f(n-1) + 2 for n ≥...
1. A function f : Z → Z is defined by f(n) = 3n − 9....
1. A function f : Z → Z is defined by f(n) = 3n − 9. (a) Determine f(C), where C is the set of odd integers. (b) Determine f^−1 (D), where D = {6k : k ∈ Z}. 2. Two functions f : Z → Z and g : Z → Z are defined by f(n) = 2n^ 2+1 and g(n) = 1 − 2n. Find a formula for the function f ◦ g. 3. A function f :...
3. For each of the piecewise-defined functions f, (i) determine whether f is 1-1; (ii) determine...
3. For each of the piecewise-defined functions f, (i) determine whether f is 1-1; (ii) determine whether f is onto. Prove your answers. (a) f : R → R by f(x) = x^2 if x ≥ 0, 2x if x < 0. (b) f : Z → Z by f(n) = n + 1 if n is even, 2n if n is odd.
Determine which of the following functions are injective, surjective, bijective (bijectivejust means both injective and surjective)....
Determine which of the following functions are injective, surjective, bijective (bijectivejust means both injective and surjective). (a)f:Z−→Z, f(n) =n2. (d)f:R−→R, f(x) = 3x+ 1. (e)f:Z−→Z, f(x) = 3x+ 1. (g)f:Z−→Zdefined byf(x) = x^2 if x is even and (x −1)/2 if x is odd.
1. For the following, make sure you explain which basic functions in F1-F3 you are using,...
1. For the following, make sure you explain which basic functions in F1-F3 you are using, and how exactly you are applying the operations O1-O3. (a) Show that every constant function g : N → N is recursive. You may need to use induction. (b) Show that the function f : N → N such that f(x) = x 3 is primitive recursive.
***************PLEASE GIVE ANSWERS IN RACKET PROGRAMMING LANGUAGE ONLY****************** Write a recursive Racket function "update-if" that takes...
***************PLEASE GIVE ANSWERS IN RACKET PROGRAMMING LANGUAGE ONLY****************** Write a recursive Racket function "update-if" that takes two functions, f and g, and a list xs as parameters and evaluates to a list. f will be a function that takes one parameter and evaluates true or false. g will be a function that takes one parameter and evaluates to some output. The result of update-if should be a list of items such that if x is in xs and (f x)...
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n ==...
QUESTION 1 For the following recursive function, find f(5): int f(int n) { if (n == 0)    return 0; else    return n * f(n - 1); } A. 120 B. 60 C. 1 D. 0 10 points    QUESTION 2 Which of the following statements could describe the general (recursive) case of a recursive algorithm? In the following recursive function, which line(s) represent the general (recursive) case? void PrintIt(int n ) // line 1 { // line 2...
java data structure question - Consider the following recurrence function" f(1)=1; f(2)=2; f(3)=3; f(4)=2; f(5)=2 f(n)...
java data structure question - Consider the following recurrence function" f(1)=1; f(2)=2; f(3)=3; f(4)=2; f(5)=2 f(n) = 2 * f(n -1) + f(n – 5) for n >= 6 Write a program to demonstrate this recurrence relation (recursive method) and demonstrate it for the values n = 6, 7, 10, and 12; Create a second method that solves the same problem using an iterative solution. Modify your test program to show that both the recursive method and the iterative methods...
1. Write 3n + 1 Sequence String Generator function (1 point) In lab5.py complete the function...
1. Write 3n + 1 Sequence String Generator function (1 point) In lab5.py complete the function sequence that takes one parameter: n, which is the initial value of a sequence of integers. The 3n + 1 sequence starts with an integer, n in this case, wherein each successive integer of the sequence is calculated based on these rules: 1. If the current value of n is odd, then the next number in the sequence is three times the current number...
For each of the following pairs of functions f and g (both of which map the...
For each of the following pairs of functions f and g (both of which map the naturals N to the reals R), state whether f is O(g), Ω(g), Θ(g) or “none of the above.” Prove your answer is correct. 1. f(x) = 2 √ log n and g(x) = √ n. 2. f(x) = cos(x) and g(x) = tan(x), where x is in degrees. 3. f(x) = log(x!) and g(x) = x log x.