Assignment 1 Its analysis of algorithm
COMP 2080 Winter 2022 Homework Assignment 1 due Wednesday, February 9, 11:59pm Must be submitted on Crowdmark, not UM Learn Proof questions will be graded for style and clarity of presentation, as well as correctness. Useful definitions and results for this assignment: • An integer x divides an integer y means: there exists an integer k such that y = x · k. We use the notation x | y to denote "x divides y" • A number p is prime means: p is a positive integer, and, there are exactly two different positive integers that divide p (and they are 1 and p). • The predicate isPrime(z) evaluates to true when z is prime, and evaluates to false when z is not prime. • Every positive integer has a unique prime factorization. One particularly useful fact you can conclude from this: if you write a positive integer x as some specific product of prime numbers, then no other prime numbers divide x . Assignment questions start here: 1.(2 pts) Translate the following English sentence into a logical statement: "Every even integer greater than 2 is the sum of two prime numbers". Your solution may only use the following: ( ) ∀ ∃ ¬ ∨ ∧ ⇒ ∈ Z > 2 · + = , x y z k isPrime 2. Consider the following logical statement S: ∀w ∈ R, (w2 − 2w 6= −1)⇒ (w 6= 1) Define P(w) to be the predicate (w2 − 2w 6= −1)⇒ (w 6= 1). (a)(1 pt) Write the converse of the predicate P(w). (b)(2 pts) Write the contrapositive of the predicate P(w). Simplify (showing each step of your work) so that your final answer does not contain a negation symbol (¬) (c)(2 pts) Write the inverse of the predicate P(w). Simplify (showing each step of your work) so that your final answer does not contain a negation symbol (¬) (d)(3 pts) Write the negation of S. Simplify (showing each step of your work) so that your final answer does not contain a negation symbol (¬) (e)(4 pts) Write an indirect proof that S is true. (f)(4 pts) Write a proof by contradiction that S is true. 1 3.(4 pts) Prove or disprove the following logical statement: ∃t ∈ R,∀x ∈ R, x · (t − 1)< 1 4.(4 pts) prove or disprove the following logical statement: ∀z ∈ z,isprime(z)⇒ ((2 | z3 − z2 + z)∨ (3 | z3 − z2 + z)) 5. our goal in this question is to prove the following identity: for all even integers q ≥ 4, q ∑ y=3 y ∑ u=0 ju 2 k = (q− 2)(2q2 + 7q+ 12) 24 to make your life easier, we’ve broken up the task into separate steps. (a)(8 pts) prove the following using strong induction: for all integers y ≥ 0: y ∑ u=0 ju 2 k = y2 4 if y is even y2−1 4 if y is odd (b)(5 pts) prove the following using strong induction: for all even integers q ≥ 4, the number of odd integers in the range [3, . . . , q] is q2 − 1. (c)(7 pts) prove the following using summation identities and previous parts of this question: for all even integers q ≥ 4, q ∑ y=3 y ∑ u=0 ju 2 k = (q− 2)(2q2 + 7q+ 12) 24 2 1="" 4.(4="" pts)="" prove="" or="" disprove="" the="" following="" logical="" statement:="" ∀z="" ∈="" z,isprime(z)⇒="" ((2="" |="" z3="" −="" z2="" +="" z)∨="" (3="" |="" z3="" −="" z2="" +="" z))="" 5.="" our="" goal="" in="" this="" question="" is="" to="" prove="" the="" following="" identity:="" for="" all="" even="" integers="" q="" ≥="" 4,="" q="" ∑="" y="3" y="" ∑="" u="0" ju="" 2="" k="(q−" 2)(2q2="" +="" 7q+="" 12)="" 24="" to="" make="" your="" life="" easier,="" we’ve="" broken="" up="" the="" task="" into="" separate="" steps.="" (a)(8="" pts)="" prove="" the="" following="" using="" strong="" induction:="" for="" all="" integers="" y="" ≥="" 0:="" y="" ∑="" u="0" ju="" 2="" k="" ="" ="" y2="" 4="" if="" y="" is="" even="" y2−1="" 4="" if="" y="" is="" odd="" (b)(5="" pts)="" prove="" the="" following="" using="" strong="" induction:="" for="" all="" even="" integers="" q="" ≥="" 4,="" the="" number="" of="" odd="" integers="" in="" the="" range="" [3,="" .="" .="" .="" ,="" q]="" is="" q2="" −="" 1.="" (c)(7="" pts)="" prove="" the="" following="" using="" summation="" identities="" and="" previous="" parts="" of="" this="" question:="" for="" all="" even="" integers="" q="" ≥="" 4,="" q="" ∑="" y="3" y="" ∑="" u="0" ju="" 2="" k="(q−" 2)(2q2="" +="" 7q+="" 12)="" 24="">