COMP 232: MATHEMATICS FOR COMPUTER SCIENCE

FALL 2015 ASSIGNMENT 4 PROBLEM 1. Use mathematical induction to show that 2n 2n+1 – 2n–1 – 1, when n is a positive integer. PROBLEM 2. The sequence of Fibonacci numbers is defined by f0 = 0, f1 = 1, and fn = fn–1 + fn–2, for n > 1. The sequence of Lucas numbers is defined by l0 = 2, l1 = 1, and ln = ln-1 + ln-2, for n > 1. Prove that fn + fn+2 = ln+1, whenever n is a positive integer, where fi and li are the ith Fibonacci number and ith Lucas number, respectively. PROBLEM 3. For each of the following relations on the set Z of integers, determine if it is reflexive, symmetric, anti-symmetric, or transitive. On the basis of these properties, state whether or not it is an equivalence relation or a partial order. (a) R = {(a, b) | a2 = b2}. (b) S = {(a, b) | | a – b | 1}. 2 PROBLEM 4. (a) Prove that {(x, y) | x - y ? Q} is an equivalence relation on the set of real numbers, where Q denotes the set of rational numbers. (b) Give [1], [1/2], and []. PROBLEM 5. Prove or disprove the following statements: (a) Let R be a relation on the set Z of integers such that xRy if and only if xy 1. Then, R is irreflexive. (b) Let R be a relation on the set Z of integers such that xRy if and only if x = y + 1 or x = y – 1. Then, R is irreflexive. (c) Let R and S be reflexive relations on a set A. Then, R – S is irreflexive. PROBLEM 6. Let R be the relation on Z+ defined by xRy if and only if x < y. Then, in the Set Builder Notation, R = {(x, y) | y - x > 0}. (a) Use the Set Builder Notation to express the transitive closure of R. (b) Use the Set Builder Notation to express the composite relation Rn, where n is a positive integer. PROBLEM 7. (a) Give the transitive closure of the relation R = {(a, c), (b, d), (c, a), (d, b), (e, d)} on {a, b, c, d, e}. (b) Give an example to show that when the symmetric closure of the reflexive closure of the transitive closure of a relation is formed, the result is not necessarily an equivalence relation.