##. Discrete Mathematical Structures ##. Justify all answers

##. Discrete Mathematical Structures ##. Justify all answers
CS2233 Discrete Mathematical Structures Homework 4 Due 11/ 02/2021 before 11:59pm Justify all answers in order to receive full credit. 1. Functions (10 points) (1) (3 points) Determine whether each of these functions f:fa; b; c; dg ! fa; b; c; d gis one-to-one and whether each of these functions is onto: (a) f(a) = b; f(b) = a; f(c) = c; f(d) = d (b) f(a ) = b; f(b) = b; f(c) = d; f(d) = c (c) f(a ) = d; f(b) = b; f(c) = c; f(d) = d (2) (3 points) Determine whether each of these functions f:R ! Ris a one-to-one correspondence (i.e., onto and one-to-one): (a) 3x + 4 (b) 3x 2 + 7 (c) (x + 2)(x 1)x (3) (1 point) Find f g and g f where f ; g:R ! Rwith f(x) = 3 x+ 4 and g (x) = x2 . (4) (3 points) Give an example of a function from Nto Nthat is: Hint: try using absolute value, oor, or ceiling for part (b). (a) one-to-one but not onto (b) onto but not one-to-one (c) neither one-to-one nor onto 2. Sequences and Summations (7 points) (1) (2 points) What are the frst 4 terms of the following sequences: (a)f( 3) n g n2N (b) f( 1) n + 1 g n2N (2) (2 points) Use index substitution to rewrite the following summation such that the index starts at 0. Then use the geometric series theorem to compute the value of the summation. 6 X i=3 ( 2) i 3 (3) (3 points) For each of the sequences below, fnd a formula that generates the sequence.(a) 4 ;10; 16;22;28; 34;40; : : : (b) 5 ;15; 45;135; 405; : : : (c) 10; 20;10;20;10; 20;10: : : Continued on the back ,! 3. Growth of Functions (11 points) (1) (4 points) Determine whether each of these functions is O(x 2 ). Proof is not required but it may be good to try to justify it (a) 100 x+ 1000 (b) 100 x2 + 1000 (c) x 3 100 1000 x2 (d) xlog x (2) (2 points) Use the de nition of to show that 5 n5 + 4 n4 + 3 n3 + 2 n2 + n 2 ( n5 ). (3) (2 points) Use the de nition of to show that 2 n3 n+ 10 2 ( n3 ). (4) (3 points) Let f ; g; h:N ! R+ . Use the de nition of big-Oh to prove that if f(n ) 2 O(h (n )) and g(n ) 2 O(h (n )) then f(n ) + g(n ) 2 O(h (n )). You should use di erent letters for the constants (i.e. don’t use cto denote the constant for each big-Oh).