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

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).