Suppose f : N→N satisestherecurrencerelation f(n + 1) (f(n) 2 if f(n)iseven 3f(n)+ 1 if f(n)isodd...

Suppose f : N→N satisestherecurrencerelation f(n + 1) (f(n) 2 if f(n)iseven 3f(n)+ 1 if f(n)isodd . Notethatwiththeinitialcondition f(0) 1,thevaluesofthefunction are: f(1) 4, f(2) 2, f(3) 1, f(4) 4, and so on, the images cyclingthroughthosethreenumbers. Thus f isNOTinjective(andalso certainlynotsurjective). Mightitbeunderotherinitialconditions?3 (a) If f satisestheinitialcondition f(0) 5,is f injective? Explain whyorgiveaspecicexampleoftwoelementsfromthedomain withthesameimage. (b) If f satisestheinitialcondition f(0) 3,is f injective? Explain whyorgiveaspecicexampleoftwoelementsfromthedomain withthesameimage. (c) If f satisestheinitialcondition f(0) 27,thenitturnsoutthat f(105) 10 and no two numbers less than 105 have the same image. Could f beinjective? Explain. (d) Prove that no matter what initial condition you choose, the functioncannotbesurjective.

Solutions

Expert Solution

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Fibonacci Sequence: F(0) = 1, F(1) = 2, F(n) = F(n − 1) + F(n −...

Fibonacci Sequence: F(0) = 1, F(1) = 2, F(n) = F(n − 1) + F(n − 2) for n ≥ 2 (a) Use strong induction to show that F(n) ≤ 2^n for all n ≥ 0. (b) The answer for (a) shows that F(n) is O(2^n). If we could also show that F(n) is Ω(2^n), that would mean that F(n) is Θ(2^n), and our order of growth would be F(n). This doesn’t turn out to be the case because F(n)...

Suppose f(1) = 2, g(1) = −1, f′(1) = 3, g′(1) = 2, f(2) = 1,...

Suppose f(1) = 2, g(1) = −1, f′(1) = 3, g′(1) = 2, f(2) = 1, and f′(2) = 0.2. Calculate the derivatives of the following functions at the provided point (be careful with using the correct values) 3 pts each: (a) d/dx (e^xf(x)) when x=2 (b) d/dx (f(x)/g(x)) when x=1 (c) d/dx (ln(xf(x))) when x=1

Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the...

Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the function f(n)? Consider the following recurrence: an= 2an-1 + 3 (where a1 = 1). Compute the values of an for n ≤ 5. Find a solution for the recurrence definition and validate its correctness. Consider the following recurrence: an=2an-1 +an-1an-2 (where a1 = 1). Compute the values of an for n ≤ 5.

2. Let f(x) ≥ 0 on [1, 2] and suppose that f is integrable on [1,...

2. Let f(x) ≥ 0 on [1, 2] and suppose that f is integrable on [1, 2] with R 2 1 f(x)dx = 2 3 . Prove that f(x 2 ) is integrable on [1, √ 2] and √ 2 6 ≤ Z √ 2 1 f(x 2 )dx ≤ 1 3 .

For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is...

For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is 1-to-1 b) Prove: f is onto c) Prove {1, 2} x N is countable

If f(n) = 3n+2 and g(n) = n, then Prove that f(n) = O (g(n))

proof: L t^(n+1)f(t)=(-1)^(n+1)(d^(n+1)/ds^(n+1))*F(s)

proof: L t^(n+1)*f(t)=(-1)^(n+1)*(d^(n+1)/ds^(n+1))*F(s)

Data Structure: 1. Write a program for f(n) = 1^2+2^3+…+n^2. (i^2 = i*i) 2. If you...

Data Structure: 1. Write a program for f(n) = 1^2+2^3+…+n^2. (i^2 = i*i) 2. If you have the following polynomial function f(n)=a0 +a1 x + a2x2+…+an xn , then you are asked to write a program for that, how do you do? 3. Write a function in C++ to sort array A[]. (You can assume that you have 10 elements in the array.) 4. Analyze the following program, tell us what does it do for each location of “???” (...

Suppose that f(x)=x^n+a_(n-1) x^(n-1)+⋯+a_0∈Z[x]. If r is rational and x-r divides f(x), prove that r is...

Suppose that f(x)=x^n+a_(n-1) x^(n-1)+⋯+a_0∈Z[x]. If r is rational and x-r divides f(x), prove that r is an integer.

Design a Turing Machine to construct the function f(n) = 4 [1/4 n] + 2, (that...

Design a Turing Machine to construct the function f(n) = 4 [1/4 n] + 2, (that is, 2 more than 4 times the integer part of 1/4 n) for n Element N. Do not just produce a TM, but also describe briefly how it works. There is a TM in the Cooper notes that does something similar. You may modify it to produce the required TM, or produce a machine totally independently.

Subjects