Posted: December 3rd, 2015

Discrete Mathematics

Discrete Mathematics

PROBLEM 1.
Use mathematical induction to show that
2
n
= 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) | a
2
= b
2
}.
(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 [p].
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 R
n
, 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.

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT