## Question

###### CPSC 121Winter 1, 2020[9 marks] In this question; WC give you three theorems; cach with "proof . Unfortunately, each proof contains mistake Find the mistake in each proof, and explain why it is mistake (you do not have to write a correct proof)_[3 marks] Theorem: If 6n2 24n + 8 2 0 then 24 Proof: when 2 4, 6n > 24, which mcans that 6n22 24n > 0, and S0 6n2 _ 24n + 8 _ 0. QED b. [3 marks] Theorem: For every positive integer a and prime p, the integer aP ~ 0 is divisible by p. Proof: We

CPSC 121 Winter 1, 2020 [9 marks] In this question; WC give you three theorems; cach with "proof . Unfortunately, each proof contains mistake Find the mistake in each proof, and explain why it is mistake (you do not have to write a correct proof)_ [3 marks] Theorem: If 6n2 24n + 8 2 0 then 24 Proof: when 2 4, 6n > 24, which mcans that 6n22 24n > 0, and S0 6n2 _ 24n + 8 _ 0. QED b. [3 marks] Theorem: For every positive integer a and prime p, the integer aP ~ 0 is divisible by p. Proof: We use proof by contradiction. Suppose that there are integers and p for which aP is not divisible by p. This is not true; WC cahl scc by picking 2 and p = 5: aP _ a = 25 _ 2 = 30 which is divisible by 5. Because the negation of the theorem is false, the thcorem must be truc_ QED [3 marks] Theorem: For any three functions f, g and h from N into Rt, if f e O(h) and g â‚¬ O(h) , then (f + g) â‚¬ O(h), where f + g is the function from N into R defined by (f + 9)(n) = f(n) + g(n). Recall that f â‚¬ O(g) if 3c â‚¬ R+ano â‚¬ NVn eN,n > no - f(n) < cg(n). Proof: Consider three unspecified functions f, and Suppose that f e O(h). which mcans that there exist values n] . C1 such that for every n 2 n1, f(n) < ch(n)_ Suppose also that g O(h) , which mCans that for every 2 n1, g(n) < ch(n). Pick c = 2C1 and no n1, and consider an unspecified positive integer 2 no. Then (f+9)(n) = f(n)+g(n) < c1h(n) + ch(n) = ch(n), required. QED