advertisement

CAS CS 131 - Combinatorial Structures Spring 2012 Problem Set #1 (Logic & Proofs, Proofs by Induction) Out: Thursday, January 26 Due: Thursday, February 2 at 2pm NO LATE SUBMISSIONS WILL BE ACCEPTED To be completed individually. 1. Classify each of the following statements as true, false, or not a proposition. Explain your answers: If the statement is a proposition, prove or disprove it. If it is not a proposition, state why. (a) An integer is a rational number. 1 (b) 5 is an even number and 16− 4 = 12 . (c) Let n denote a positive integer. (d) If a and b are integers with a − b ≥ 0 and b − a ≥ 0, then a = b. 2. Determine whether the statement is true or false. Explain your answers. (a) 5 ⊂ {1, 2, 3, 4, 5} (b) 3 ∈ {1, 2, 3, 4, 5} (c) {3, 5} ∈ {1, 2, 3, 4, 5} (d) {3, 5} ⊂ {x|(x = 2 ∗ k + 1) ∧ k ∈ N} 3. Prove that the equations 2x + 3y − z = 5 x − 2y + 3z = 7 x + 5y − 4z = 0 have no solution. (Give a proof by contradiction.) 4. Prove that the sum of a rational and an irrational number is irrational. (Use proof by contradiction.) 5. Use induction to prove that 12 + 22 + . . . + n2 = for every natural number n. 1 n3 n2 n − + , 3 2 6