CmSc 175 Discrete Mathematics

Study Guide Unit Exam 3

Unit exam 3 will cover proof problems on equivalence relations and partial order relations, proof problems on Math induction, functions, sequences, and counting.

Here are sample problems:

  1. Equivalence and partial order relations
  1. Let R  A x A be a binary relation as defined below. In which cases R is a partial order? A total order?
  1. A = the positive integers; (a,b)  R iff b is divisible by a
  1. A = N x N; ((a,b),(c,d) )  R iff a  c or b  d.
  1. A = N; (a,b) R iff b = a or b = a+1
  1. A is the set of all English words; (a,b)  R iff a is no longer than b
  1. Define a relation R on N x N :

R = { ((a, b), (c, d)) | a + d = b + c}

Show that R is an equivalence relation on N x N

  1. Define a relation R on N x N :

R = { ((a, b), (c, d)) | a + b = c + d}

Show that R is an equivalence relation on N x N

  1. Define a relation R on N x N :

R = { ((a, b), (c, d)) | ad = bc}

Show that R is an equivalence relation on N x N

  1. Define a relation R on N x N :

R = { ((a, b), (c, d)) | ab = cd}

Show that R is an equivalence relation on N x N

  1. Define a relation R on N :

R = { (a, b) |  integer q, b = qa, i.e. b is a multiple of a}

Show that R is partial order relation on N

  1. Let S be a collection of sets. Define a relation R on S:

R = {(s1, s2) | s1  s2}

Show that R is a partial order relation on S

  1. Let R1 and R2 be any two partial orders on the same set A. Prove that R1  R2 is a partial order
  1. Let R1 and R2 be any two equivalence relations on the same set A.

Prove that R1  R2 is an equivalence relation.

  1. Let R1 and R2 be any two transitive relations on the same set A. Will R1 R2 be a transitive relation ?
  1. Math induction
  1. Let S(n) = 1 + 2 + 3 + … + n

Prove P(n): S(n) = n(n + 1)/2 for all n  1

  1. Let S(n) = 1 + 3 + 5 … + (2n – 1)

Prove P(n): S(n) = n2 for all n  1

  1. Let S(n) = 2 + 4 + 6 … + 2n

Prove P(n): S(n) = n(n + 1) for all n  1

  1. Let S(n) = 12 + 32 + 52 + …. + (2n-1) 2

Prove P(n): S(n) = n(2n – 1)(2n + 1)/3 for all n  1

  1. Let S(n) = 1 + a + a2 + a3 + …. + a(n-1)

Prove P(n): S(n) = (an – 1)/(a-1), for all n ≥1, a ≠ 1

  1. Let S(n) = 1 + 2 + 22 + 23 + …. + 2n

Prove P(n): S(n) = (2n+1 – 1) for all n ≥0

Note that in this problem you have to prove P(0) in the base step

  1. Let S(n) = 1 + 5 + 9 + … + (4n – 3). Prove P(n): S(n) = n(2n – 1) for all n  1
  1. Let S(n) = 2 + 6 + 18 + …. + 2*3(n-1)

Prove P(n): S(n) = 3n – 1, for all n ≥1

  1. Let S(n) = 3 + 6 + 9 + 12 + 15 + …. + 3n

Prove P(n): S(n) = 3n(n+1)/2 for all n  1

  1. Let S(n) = 1*2 + 2*3 + 3*4 + …. + n(n+1)

Prove P(n): S(n) = n(n+1)(n+2)/3 for all n ≥1

  1. Let S(n) = 1 / (1*2) + 1 / (2*3) + … + 1 / n(n + 1)

Prove P(n): S(n) = n / (n+1) for all n ≥1

  1. Let S(n) = 1 / (1*3) + 1 / (3*5) + … + 1 / (2n – 1)(2n + 1)

Prove P(n): S(n) = n / (2n + 1) for all n  1

  1. Let S(n) = 1* 1! + 2*2! + 3*3! + … + n*n!

Prove P(n) : S(n) = (n+1)! – 1 for all n  1

  1. Let Q(n) = (1 – ½)(1 – 1/3)…..(1 – 1/(n+1))

Prove the statement P(n): Q(n) =1/(n+1), for all n ≥1

  1. Let Q(n) = ( 1 – 1/22)*(1 – 1 /32)* ….*(1 – 1/n2)

Prove P(n) : Q(n) = (n+1)/2n for all n  2

  1. Functions and sequences

Problems as in HW08

  1. Counting

All problems in the handout on counting, see also the posted solutions.

Sample solutions:

Problem A.5:Define a relation R on N x N :

R = { ((a, b), (c, d)) | ab = cd}

Show that R is an equivalence relation on N x N

Reflexivity.

To show reflexivity, we need to show that ((a,b),(a,b) is in R for any (a,b) in N x N.

Since ab = ab (by basic algebra), and by the definition of R, we have ((a,b),(a,b) in R

Therefore R is reflexive

Symmetry. In order to show symmetry, we have to show that

If ((a,b),(c,d)) is in R, then ((c,d),(a,b)) is also in R.

In order to show that ((c,d),(a,b)) is in R we need to show that cd = ab.

Let ((a,b),(c,d)) be in R.

By the definition of R, we have ab = cd , therefore cd = ab.

By the definition of R ((c,d),(a,b)) is in R

Therefore R is symmetric

Transitivity.

In order to show transitivity, we need to show that

If ((a,b),(c,d)) is in R and ((c,d),(e,f)) is in R, then ((a,b),(e,f)) is also in R.

In order to show that ((a,b),(e,f)) is in R we need to show that ab = ef

Let .((a,b),(c,d)) be in R

By the definition of R, ab = cd (1)

Let ((c,d),(e,f)) be in R.

By the definition of R, cd = ef (2)

From (1) and (2) we have ab = cd = ef, therefore ab = ef.

Therefore ((a,b),(e,f)) is in R.

Therefore R is transitive.

We have shown that R is reflexive, symmetric and transitive, therefore R is a relation of equivalence.

Problem A.6Define a relation R on N :

R = { (a, b) |  integer q, b = qa, i.e. b is a multiple of a}

Show that R is partial order relation on N

a. Anti-symmetry. In order to show that R is anti-symmetric we need to show that

If (a,b) is in R and a≠ b, then (b,a) is not in R.

Let (a,b) be in R. By the definition of R, there is an integer q such that

b = qa.

Solving for a, we get

a = b * (1/q)

q is a n integer, therefore 1/q is not an integer. Note that if q = 1, then a = b and we want a≠ b

Therefore (b,a) is not in R, therefore R is antisymmetric.

b. Transitivity.

In order to show that R is anti-symmetric we need to show that

If (a,b) is in R and (b,c) is in R, then (a,c) is in R.

Let (a,b) be in R and (b,c) be in R.

By the definition of R this means that there are integers q and r such that

b = qa, c = rb

Therefore c = rqa. Let p = rq, p is integer.

Therefore c = pa, i.e. c is a multiple of a

By the definition of R (a,c) is in R

Therefore R is transitive.

Being anti-symmetric and transitive, R is a partial order relation.

Problem A.9.Let R1 and R2 be any two equivalence relations on the same set A.

Prove that R1  R2 is an equivalence relation.

a. Reflexivity

In order to show reflexivity, we need to show that for all aA, (a,a) is in R1  R2

Direct proof:

R1 is a reflexive relation, therefore all pairs of type (a,a) are in R1.

R2 is a reflexive relation. Therefore all pairs of type (a,a) are in R2.

Therefore all pairs of type (a,a) are in R1  R2, therefore R1  R2 is reflexive

b. Symmetry

In order to show symmetry, we need to show that

for all a, bA, if (a,b) is in R1  R2 then (b,a) is in R1  R2

Proof by contradiction

Assume that there are two elements a and b such that (a,b) is in R1  R2 but (b,a) is not.

(a,b) in R1  R2 means that (a,b) is in R1. R1 is symmetric, therefore (b,a) is in R1

(a,b) in R1  R2 means that (a,b) is in R2. R2 is symmetric, therefore (b,a) is in R2.

Since (b,a) is in R1 and in R2, it has to be in R1  R2

This contradicts aour assumption that (b,a) is not in R1  R2.

Therefore R1  R2 is symmetric.

c. Transitivity

In order to show transitivity, we need to show that

for all a, b, c A, if (a,b) is in R1  R2 and (b,c) is in R1  R2, then (a,c) is in R1  R2

Proof by contradiction.

Assume there are three elements a, b, and c such that (a,b) and (b,c) are in R1  R2 but (a,c) is not in R1  R2.

(a,b) and (b,c) are in R1  R2. This means (a,b) and (b,c) are in R1.

R1 is transitive, therefore (a,c) is in R1

(a,b) and (b,c) are in R1  R2. This means (a,b) and (b,c) are in R2.

R2 is transitive, therefore (a,c) is in R2.

Since (a,c) is in R1 and in R2, it must be in R1  R2. This contradicts our assumption that (a,c) is not in R1  R2.

Therefore R1  R2 is transitive.

Therefore R1  R2 is a relation of equivalence.

Problem A.10.Let R1 and R2 be any two transitive relations on the same set A.

Will R1 R2 be a transitive relation?

We don’t know. It might be.

Example: A = {a,b,c}, R1 = {(a,b)}, R2 = {(a,c)}. R1 R2 = {(a,b), (a, c)}.

R1 R2 is transitive.

However, the union might be not transitive. Example: A = {a, b, c}

R1 = {(a,b)}, R2 = {(b,c)}, R1 R2 = {(a,b), (b, c)}. Here the union is not transitive.

Mathematical Induction

Problem B.12 Let S(n) = 1 / (1*3) + 1 / (3*5) + … + 1 / (2n – 1)(2n + 1)

Prove P(n): S(n) = n / (2n + 1) for all n  1

Base step:Show that P(1): S(1) = 1/(2 + 1) is true.

S(1) = 1/(2 + 1) = 1/3

By the definition of the sum, S(1) = 1/(1*3) = 1/3

Therefore P(1) is true.

Inductive step

We will show that the conditional P(k)  P(k+1) is true.

P(k): S(k) = k / (2k +1)

P(k+1): S(k+1) = (k+1)/(2(k+1) + 1) = (k+1)/(2k + 3)

Assume P(k) is true, i.e. S(k) = k / (2k +1)

S(k+1) = S(k) + 1 / (2(k+1) – 1)(2(k+1) + 1) =

=k / (2k +1) + 1 / (2k + 1)(2k + 3) =

= k(2k + 3)/(2k + 1)(2k + 3) + 1 / (2k + 1)(2k + 3) =

= [ k(2k +3) + 1 ]/ (2k + 1)(2k + 3) =

(2k2+3 k +1) / (2k + 1)(2k + 3)

(2k2 +3 k +1) = (k+1)(2k + 1) (see the note at the end)

(2k2 +3 k +1) / (2k + 1)(2k + 3) = (k+1)(2k + 1) /(2k + 1)(2k + 3) = (k+1) / (2k + 3)

Therefore P(k+1) is true

Therefore P(k)  P(k+1) is true

By the principle of math induction P(n) is true for all n 1

Note: How did I know that (2k2 +3 k +1) = (k+1)(2k + 1) ? This is not very obvious.

I looked at my goal:

S(k+1) = (k+1)/(2k + 3)

But I have (2k2 +3 k +1) / (2k + 1)(2k + 3)

If (2k2 +3 k +1) = (k+1)(2k +1), then I will have

S(k+1) = (k+1)(2k +1) / (2k + 1)(2k + 3) = (k+1)/(2k + 3), i.e. I will prove my goal.

What remains is simply to multiply (k+1)(2k +1) and see if it is equal to (2k2 +3k +1)