YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 1. (5+5 points) (a) Prove that log(pm + 1) is O(log r) for all m e Et. (b) Give as good a big-O estimate as possible (in terms of the standard reference functions) for the function (n! + 2")(n' + log(n' + 1)). Date: Nov 21, 2022, Crowdmark submission Due date Nov 26, 2022.N YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 2. (5+5 points) (a) Prove by mathematical induction that for all positive integers n Ck. 2k = (n -1). 2+1 + 2 (b) Prove by induction that 3" 6.YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 3 3. (5+5 points) (a) For the Fibonacci sequence defined recursively by fo = 0, f1 = 1, and fn+1 = fn + fn-1 for all n 2 1 prove by structural induction that fitf? + ... + fh = faint1 (b) Use Strong Induction to show that every positive integer n can be written as the sum of distinct powers of 2: 20 = 1, 21 = 2, 22 = 4, 23 = 8, etc. Hint: For the inductive step, separately consider the case where k + 1 is even, hence (k + 1)/2 is an integer, and where it is odd)4 YORK UNIVERSITY SC/MATH 1.019 3.0 D WRITTEN ASSIGNMENT #2 4. (10 points) Find the recurrence relation and initial conditions for the number an of ternary strings of length n (i.e containing only 03, 13 and 23) that do not contain two consecutive Us. What is the value of a5? YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 5 5. (5+5 points] (a) Solve the recurrence relation an = 4on4 + 4an_2 with initial conditions as = 1 and a1 = 2. (b) Find all solutions of the recurrence relation on = 2on4 + 3 - 2\". 6 YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 6. (10 points) Let R be a binary relation on a set A that is reexive and transitive. Prove that R\" = R for all positive integers n. 7. (5+5 points] (a) Show that a binary relation R on a set A is antisymmetric if and only if R 0 R'1 Q A where A = {{o,a)|a E A} is the diagonal (equality) relation . (b) Let R be the binary relation on a set A = {(11, a2, {:3} represented by the matrix 0 1 0 NIB: 0 1 1 1 0 1 Find the matrix DAR1 representing the relation R'l. YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 8. (5+5 points) (a) Suppose A is a nonempty set and f : A - B is a function on A. Let R be the binary relation on A defined by R := {(x, y) E A X A f(x) = f(y)}. Show that R is an equivalence relation on A and describe the equivalence classes of R. (b) Give a description of congruence classes modulo 5 on Z (i.e. the equivalence classes of the congruence equivalence relation Rs := {(m, n) EZ x Z |m = n (mod 5)}).8 YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 9. (5+5 points) (a) Can a pseudograph with 115 vertices each of degree 7 exist? Explain. (b) Draw the simple undirected graphs K7,, C7, W7, Q4 and K4,4. Which of them are bipartite? Give reasons for your answers.YORK UNIVERSITY SC/MATH 1019 3.0 D WRITTEN ASSIGNMENT #2 9 10. {5+5 points) (a) For which values of n are the graphs Kn, Cm Wu and 62,.1 bipartite? Give reasons for your answers. (b) Prove that in a simple graph with at least 2 vertices there must he a pair of vertices of the same degree