Discrete Structures Homework

COT-3100 Discrete Structures, Spring 2018

Assignment 2: Chapters 2,3,4 & 5

Due Date: March 2nd at 11:55 PM

• The solutions should be written (or typed) on letter-sized (8.5′′ × 11′′) papers. Solutions written on any other type of papers will NOT be considered for eval- uation.

• Please submit your answer in the form of a single pdf file ONLY.

• If your solution is typed in Word document, you can simply use the MS Word to simply save the word file as a pdf one.

• In the case that your solution is hand-written on letter-sized (A4) papers, you need to:

– first, scan each page (or take a picture of each page);

– second, add all of the taken pictures to a blank Word document;

– and finally, save the Word document as pdf format.

1. (6 points) Write the following statements using predicates, math symbols, ∀, ∃, etc.

(a) The sum of square roots of any four real positive numbers is not less than the square root of their sum.

(b) Any positive integer greater than 1 can be written as the product of finite number of prime numbers.

2. (6 points) State the contrapositive, converse, and inverse of the following conditional statements:

(a) If the gold price increases, then, the oil price decreases.

(b) If you become vegetarian, then, you will lose weight.

3. (6 points) State the negation of the following statements:

(a) For every real number x, if x is rational, then, x2 is rational.

(b) ∀m,n ∈ Z,∃q ∈ Q ∃r ∈ Z such that if m = nq + r, then q ∈ Z

4. (10 points) By constructing an appropriate truth table, test the validity of the following arguments:

1

(a)

p→∼ (q ∨ r) ∼ q → p ∨ r

∴ r → q

(b)

q → p ∼ p q

∴ c

5. (6 points) For the following pairs of predicates P and Q, prove or disprove the state- ments P ⇒ Q, Q⇒ P , and P ⇔ Q.

(a) P (x) : “x is prime and 1 < x < 10”, Q(x) : “x is an odd positive integer less than 9”, and domain of x in both predicates P and Q is Z+.

(b) P (x, y) : “xy is a positive integer”, Q(x, y) : “y is a rational number”, domain of x in both predicates P and Q is Z, and domain of y in both predicates P and Q is R.

6. (36 points) In each part, use the given method to prove/disprove the statements:

(a) (4 points) Disprove the following statement by finding an appropriate counterex- ample:

For every real numbers x, y, and z, if x > 0, y > 0, and z > 0, then

10−3z + x2 + y2 + z2 ≤ (x+ y + z)2.

(b) (7 points) Use the method of exhaustion to prove the following statement:

“For every prime number p between 30 and 58, 10 does not divide p− 9.”

(c) (8 points) Using the method of constructive proof of existence, prove the following statements:

i. 0.17461746 . . . is rational (digits 1746 in the fractional part are repeated for- ever).

ii. For every positive integer n, n2 + 4n+ 3 is not prime.

(d) (6 points) Using the method of proof by division into cases, prove that for every integer n, (n+ 4)2 is not prime.

(e) (6 points) Use the method of direct proof to prove the following statement:

∀m,n, k, l ∈ Z, (m|n ∧ k|l)→ (mk|nl)

2

(f) (5 points) Using the method of proof by contradiction, prove that there is no smallest positive rational number.

7. (6 points) Let bi represent the term with index i of the following sequence: 4,-1,4,- 3,2,1,6,-2 Also, assume that the sequence domain is {−4, −3, . . . , 3}. Compute the following expressions:

(a) 6∑

i=4

b3i−15 (b) 2∑

k=0

k∏ i=−3

b2i

8. (8 points) Use mathematical induction to prove that n∑

i=−n (2)i = (2

2n+1−1) 2n

.

9. (16 points) Let an be a sequence such that a0 = 2, a1 = 8, a2 = 10 and ak = 3ak−1 + ak−2 − 3ak−3 for every k ≥ 3.

(a) (6 points) Assuming that the following equation represents the general formula of the sequence an, find the values of α, β, and γ.

an = α(−1)n + β3n + γ ∀ integer n ≥ 0 (1)

(b) (10 points) Use the strong induction to prove that Eq. 1 is the general formula for the sequence an.

3