Class Notes (837,614)
Canada (510,370)
Mathematics (1,919)
MATH 135 (334)
Lecture

MATH135 - September 9-November 13, 2013

34 Pages
76 Views
Unlock Document

Department
Mathematics
Course
MATH 135
Professor
Ross Willard
Semester
Fall

Description
⇚ Return to University Notes index MATH 135 Mathematical proofs. Section 004 Instructor: Name: Ross Willard Email: [email protected], [email protected] Office Hours: Tuesdays 9:00AM-10:00AM , Fridays 1:00PM-2:00PM, in MC 5058 Tutorials: Tuesdays 4:30PM-7:20PM (Drop-in to Biology 1 Room 271) 9/9/13 Show √ x(x − √ x) = x(1 − √ x) : √ √ √x x − √ x) = √ √ x(1 − √ x) √ √ √( x − 1) = √ √ x(1 − √ x) This proof is invalid. Proofs: Avoid starting with thing trying to be proved (assuming the thing is true) Use english sentences to give details. Prove thax ≥ 2x ▯ x ≤ 0 ∧ x ≥ 2 : Let x re2resent a real number. ;start by declaring assumptions Assume x ≥ 2x . Thenx − 2x ≥ 0 . Thenx(x − 2) ≥ 0 . This implies that ex ≥ 0 and x ≥ 2, or thx ≤ 0 and x ≤ 2. Ix ≥ 0 and x ≥ 2, thex ≥ 2 . Ix ≤ 0 and x ≤ 2, thex ≤ 0 . In conclusix ≤ 0 andx ≥ 2 ifx ≥ 2x . Check the converse: Assume x ≤ 0, thex ⋅x ≥ 0 and 2x ≤ 0. Thereforex ≥ 2x . Assume x ≥ 2, thex ⋅x >= 2x . 2 Thereforex ≥ 2x . 2 In conclusix ≤ 0 andx ≥ 2 if and onlyx ≥ 2x . 1 Show x + x>= 2 for alx > 0: Letx represent a positive real number. Certainly(x − 1) ≥ 0 is true. 2 So x − 2x + 1 ≥ 0 . Thus x − 2x + 1 + 2x ≥ 0 + 2x , and is equivalent tx + 1 ≥ 2x . 2 1 Sincex > 0 ,x + 1 ≥ 2x is equivalent x + x ≥ 2 . Hence x + 1 ≥ 2 , which was to be proved. x In handwriting, ▯ (double right arrow) is considered an acceptable replacement for "Therefore", "Hence", "Then", "Thus". A proposition is a true statement, proved with a valid argument. A theorem is an important or significant proposition. A lemma is a helper proposition used in the proof of a theorem. A corollary is a proposition that follows almost immediately from a theorem. An axiom is a statement is assumed to be true, no proof needed. Propositions are derived from these. Summary Written solutions are primarily done in English. Proofs start with relevant assumptions or known true statements, and ends with the thing to be proved. 11/9/13 2 2 Show (x + y) − (x − y) = 4xy : Let x and y represent real numbers. 2 2 2 2 2 2 Clearly,(x + y) − (x − y) = x + 2xy+ y − (x − 2xy+ y ) . Clearly,x + 2xy+ y − (x − 2xy+ y ) = x + 2xy+ y − x + 2xy− y 2 2 2. 2 2 2 2 Clearly,x + 2xy+ y − x + 2xy− y = 2xy+ 2xy . Thus, (x + y) − (x − y) = 4xy by transitivity of equality. In the interests of style, multiple equalities can be written thus: Let x and y represent real numbers. 2 2 2 2 2 2 Clearly,(x + y) − (x − y) = 4xy = x + 2xy+ y − (x − 2xy+ y ) , ⇒ x + 2xy+ y − (x − 2xy+ y ) = x + 2xy+ y − x + 2xy− y 2 2 2, 2 2 2 2 ⇒ x + 2xy+ y − x + 2xy− y = 2xy+ 2xy . Thus, (x + y) − (x − y) = 4xy by transitivity of equality. (here,, means "which in turn") Only statements can imply other statements. Statements are sentences that can be true or false. They are complete sentences with subject(s) and verb(s). 2 + 2 = 4 (true statement: subject verb subject verb subject) 2 The equation x − 1 = 0 has 2 distinct real roots (true statement: subject verb subject) x > 0 (context required: open sentence) Compound statements are composed of several component statements: 0 < x < 1 Which is in fact: 0 < x and x < 1 abs(x) = 2 Which is in fact: 0x = 2 or x = -2 If A and B are statementsA∧ Ben(Awedge B) meansA"and B". If A and B are statementsA∨ Ben(Avee B) means A andB ". If A and B are statementsA ▯hen B A impliesB) meansB"is true wheAis true". The general fhypothesis implieconclusion. When proving with this, it is only necessary to prove that it is impossible for the hypothesis to be true but the conclusion to be false. For example, one can simply prove the hypothesis is always false, or the conclusion is always true. These statements commonly take the following forms: A implieB . IA , theB. AsA , therefBr. AsA , hencB. If 1 = 2, then 1 = 0. This implication is true, since the hypothesis is false. Implications are always true as long as the hypothesis is not true while the conclusion is false. If A and B are statementsA ▯hen B (A if and onlB) means A is true only wBeis true". T represents trFerepresents false. IfAis a statement, ¬Aen(notA) means "noA". Laws of Logic A∧ (B∨ C) ≡ (A∧ B)∨ (A∧ C) A∨ (B∧ C) ≡ (A∨ B)∧ (A∨ C) - distributivity law A∧ B ≡ B∧ A A∨ B ≡ B∨ A - commutativity law (A∧ B)∧ C ≡ A∧ (B∧ C) (A∨ B)∨ C ≡ A∨ (B∨ C) - associativity law Truth tables Truth tables show the truth value of a compound statement by determining the values of the component statements. Two statementA and B are logically equivalent if and only if they have the same truth values in the truth table. We write A ≡ B to represent this. AreA ▯ B and(¬A)∨ B logically equivalent? A B A ▯ B (¬A)∨ B T T T T T F F F F T T T F F T T Since both have the same truth table values, they are logically equivalent. 13/9/13 If an intemerdivides intenewithout any remainder, we m ∣ n. In other wo∃k ∈ Z,n = km . 3 ∣ - True statemen6 = 2 ⋅3 7 4 ∣ - False stateme7 =- 4⋅4 0 ∣ - True statemen0 = 0 ⋅0 1 1|2 is a statement, whileis an operation. 2 Sets A set is a collection of objects. The objects are called elements or members. Elements can be anything: numbers, letters, functions, cats, or even themselves sets. Notation:A = {2,4,6,8} ,B = {1,2,…,98,99} Conventionally, we use capital letters to name identifiers that are sets. Common sets: N - natural numbers{1,2,3,…} Z - integers {…,−2,−1,0,1,2,…} R - real numbers Q - rational numbers - Q¯¯- irrational numbers C - complex numbers ∅ - empty set An object belongs to a set if it is an elema ∈ Bf means "a is an element of B". All sets contain the empty set. A statement is a sentence that is either true or false. As a result, the following are not statements: 6 ∣ x x + 1 > 0 x ∈ {2,4,6,8} Are these true or false? It is not possible to know, since txeis unknown. An open sentence appears to be a statement, but contains unknowns (variables). In order to be a statement, the sentence must be viewed in a context where all these unknowns are given a value in their domain, and is either true or false when this is done. A variable is a symbol that always represents an element or elements from a designated set known as the domain. Set builder notation is used when there are too many elements in a set to list all of them. One way of writing it is as follows (type I): {x ∈ R 0 ≤ x < 2} {x ∈ N : 6 ∣ n} = {6,12,18,24} {var ∈ domain ( or : ) open_sentence} "Set ovar in domain such thatopen sentence " There is another set builder notation (type II): {3n+ 1 n ∈ N} = {4,7,10,13,…} x { ∣n ∈ N } = [−0.5,0.5] x + 1 ∣ {function(var) ( or : ) var ∈ domain} "Set of values function(var) as var ranges overdomain " All other forms of set builder notation are incorrect. {n ∈ N n ∈ N} - valid type I set builder notation; "set of those natural numbers that belong to the set of real numbers" {x x ∈ R} - valid type II set builder notation; "set of all x such that x is a real number" 16/9/13 Basic Set Operations The union ofA and B isA∪ B . This is the set of all elements belongingAtoorBt. This can be written as x ∈ A∪ B ▯ x ∈ A∨ x ∈ B , and is sometimes definedA∪ B = {x ∣ x ∈ A∨ x ∈ B} . The intersection oA and B isA∩ B . This is the set of all elements belonging to both A and B. This can be written as x ∈ A∩ B ▯ x ∈ A∧ x ∈ B , and is sometimes definedA∩ B = {x ∈ A x ∈ B} . The difference oA and B isA− B or A∖ B . This is the set of all elements beloAg, but not B. This can be written ax ∈ A− B ▯ x ∈ A and x ∉ B , and is sometimes definedA− B = {x ∈ A x ∉ B} . The complement of a setA isA¯. This is the set of all elements in the universe of discourse thA. are not in The cardinality of a Aeis∣A∣. This is the number of elements it contains. We can construct a truth table of these operations: x ∈ A x ∈ B x ∈ A∪ B x ∈ A∩ B x ∈ A− B T T T T F T F T F T F T T F F F F F F F Two sets are equal if and only if they have exactly the same {1,2,3} = {3,2,1} : "A is equal to B"). Inclusion: a set is a subset of another if every element of the first set is also containe{1,2} ⊆ {3,2,1} s:t ( "A is a subset of B"). In other∀x ∈ A,x ∈ B . If a set is a subset of another, the second set is a superset of the first. A set is a proper subset of another if it is a subset and it{1,2} ⊂ {3,2,1} : "A is a proper subset of B"). The number of subsets of any se2 , wheren is the number of elements in the set. List all the subse{a,b,c} : We create a list of tuples of 0 and 1 of length 3, each one unique: (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) . This can be done via binary counting. Each position in the tuple corresponds to one element of the set. For example, position 1 a,rresponds to position 2 corresponds b, and position 3 correspondc.to For each tuple, we construct a set that contains only those elements that correspond to positions that have the value 1 in the tuple. These se∅,{c},{b},{b,c},{a},{a,c},{a,b},{a,b,c} . These are the subsets of th{1,2,3} . Proving a statement of the fA ⊆ B : Let x be /assume x is a random/arbitrary/representative element of A Argue that x must be an element of B. This prove∀x,x ∈ A ▯ x ∈ B , which provA ⊆ B . Prove{n ∈ N : 4 ∣ n} ⊆ {n ∈ N : 2 ∣ n}: LetA represent the first set. LetB represent the second set. Letx be an arbitrary element of A. Lety be an arbitrary element of B. Given that for A, ∈ N and 4 ∣ x, we know that there must exist an integersuch thatx = 4k . Given that for B, ∈ N and 2 ∣ y, we know that there must exist an integersuch thaty = 2k . Clearly,x = 2(2k) . So there must exist an integer′ such thatx = 2k ′; namely,k = 2k . Hence x ∈ N and 2 ∣ x. Therefore,x ∈ B . Since x is arbitrary,,x ∈ A ▯ x ∈ B . Proving a statement of the formA = B has two general techniques: Technique 1: proveA ⊆ B , and then provB ⊆ A , using the above strategy: "prove thAt and B are sets, A− B = A = (A∩ B) ". Let x be an arbitrary element oA . So x ∈ A and x ∉ B . Ifx ∈ A∩ B , thex ∈ A and x ∈ B . However, we know that x ∉ B . Therefore,x ∉ A∩ B . Since x ∈ A and x ∉ A∩ B ,x ∈ A− (A∩ B) . Since x ∈ B ∀x ,A− B ⊆ A− (A∩ B) . Now we prove the reverse. Let y be an arbitrary element oA− (A∩ B) . Sox ∈ A and x ∉ A∩ B . So (by DeMorgan's Law) x ∉ A , ox ∉ B . However, x ∈ A , sox ∉ B . Since x is representativ∀x,x ∈ (A∩ B) , andA− (A∩ B) ⊆ A− B . Since both sides are subsets of or equal to each other, they are equal. 18/9/13 Technique 2: Prove that∀x,x ∈ A ▯ x ∈ B : Let x be an arbitrary object. Ifx ∈ A , thex ∈ B . Ifx ∉ A , thex ∉ B . Therefore,x ∈ A ▯ x ∈ B . Prove that for any setR ,S T R∩ (S ∪ T) = (R∩ S)∪ (R∩ T) . Let x be an arbitrary object. We know that x ∈ R∩ (S ∪ T) ▯ x ∈ R∧ (x ∈ S ∨ x ∈ T) . Recall thatP ∧ (Q ∨ R ≡ (P ∧ Q)∨ (P ∧ R) . Clearly,x ∈ R∧ (x ∈ S ∨ x ∈ T) ▯ (x ∈ R∧ x ∈ S)∨ (x ∈ R∧ x ∈ T) . This technique is only usable in certain situations. At other times, technique 1 is a better choice. A ≡ B is not equality, it works on two logical proposiAioand B . Quantifiers Two common phrases in math: Universal:open sentence for alsomething ; for eversomething ,open sentence . Existentialopen sentence for some [something]; there exists a [something] such that statement. This can be written using quantifier symbols: ∀x ∈ R.x ≥ 0 2 For every element x in the seR , it is true x ≥ 0 . In short, for every real numbex,x ≥ 0 . ∃x ∈ R,x − 3x + 2 = 0 2 There exists an elementx in the seR such thatx − 3x + 2 = 0 . 2 − 3x + 2 = 0 In short, there exists a real numxesuch thatx − 3x + 2 = 0 . Quantifiers are not part of the hypothesis or conclusion - they are se∀x,P(x) ▯ Q(x) is the same as writing ∀x,(P(x) ▯ Q(x)) . The hypothesis would beP(x) and the conclusion would beQ(x) . A quantified statement takes the form of(∀ or ∃)x ∈ S,open sentence . Negating a statement: A -f(x) has a real root. ¬A -f(x) does not have a real root. B - every integer is even. ¬B - some integer is not even. Formally: A : ∃x ∈ R,f(x) = 0 ¬A : ∀x ∈ R,f(x) ≠ 0 B : ∀x ∈ Z,2 ∣ x ¬B : ∃x ∈ Z,2 ∤ x Negate the statement every even integer is a power of 2 . A : ∀x ∈ Z,2 ∣ x ▯ x is a power of 2 . ¬A : ∃x ∈ Z,¬(2 ∣ x ▯ x is a power of 2) . Recall that¬(P ▯ Q) = P ∧ ¬Q . So the above is equivalent t¬A : ∃x ∈ Z,2 ∣ x ▯ x is not a power of 2 . There exists an integer which is even but is not a power of 2. General rules for negation: ¬(∀x ∈ S,P) ≡ ∃x ∈ S,¬P ¬(∃x ∈ S,P) ≡ ∀x ∈ S,¬P ¬(P ∧ Q) ≡ (¬P)∨ (¬Q) - DeMorgan's law ¬(P ∨ Q) ≡ (¬P)∧ (¬Q) - DeMorgan's law ¬(P ▯ Q) ≡ P ∧ (¬Q) ¬(P ▯ Q) ≡ P ▯ (¬Q) Proving quantified statements To prove ∀x ∈ S,P , use the select method: Let x be an arbitrary/representative/random element oS . Prove thatx makes P true. Prove A∩ B ⊆ A : We must prove that ∀x ∈ A∩ B,x ∈ A . Let x be a representative element A∩ B . So x ∈ A and x ∈ B . Since P holds for any representative elemenx ,∀x ∈ A∩ B,x ∈ A . Therefore,A∩ B ⊆ A . To prove ∃x ∈ S,P , use the construct method: Construct/define/exhibit a specific elemxntofS . Show that P is true for txi. Since x satisfiex ∈ S , this prove∃x ∈ S,P . Prove that8 ∣ (2013 − 1) : 2 In other wo2ds, we must prove∃k ∈ Z,8k = 2013 − 1 . Note: 2013 − 1 = (2013 + 1)(2013 − 1) = 8 ⋅1007 ⋅503 . Let k represent1007 ⋅503 . So 8k = 4(503)⋅2(1007) , o(2013 − 1)(2013 + 1) . 2 Clearly, this is equivalen2013 − 1 . 2 − 1 Then there exists an integer multiple of 8 eq2013 − 1 . 2 Therefore,8 ∣ (2013 − 1) . ;wip: read chapter 14, 15, 10, 11 by Sept. 23 Prove or disprove that every real number has a real square root: LetA represent the statement. In other woAdis∀x ∈ R,∃y ∈ R,y = x2 (for every real numbex, there 2 exists a real numbeysuch thaty = x ). 2 The negation of the stateme¬A is∃x ∈ R,∀y ∈ R,y ≠ x . By proving the negation true, we can prove the statement false. Note: construct method Constructx = −1 . Note: select method Lety be a random element ofR . Then y ≥ 0 . 2 So y ≠ −1 . 2 As y is an arbitrary real number, this p∀y ∈ R,y ≠ x . Sincex satisfiex ∈ R , this prove∃x ∈ R,∀y ∈ R,y ≠ x . Therefore,¬A is true, aAdis false. In order to prove something false, we generally need to prove its negation true. Prove or disprove that for every real number, there is some integer greater than it: LetA represent the statement. In other wordsA is∃n ∈ Z,∀x ∈ R,n > x . The negation of the stateme¬A is∀n ∈ Z,∃x ∈ R,n ≤ x . By proving the negation true, we can prove the statement false. Note: select method Len be a random element ofZ . Note: construct method Lex = n . Certainlyx ∈ R , andn ≤ x . Sincex satisfiex ∈ R , this prove∃x ∈ R,n ≤ x . As n is a random element oZ , this prov∀n ∈ Z,∃x ∈ R,n ≤ x . 23/9/13 Implications An implication is a compound statement of the foP ▯ Q (P impliesQ ). The hypothesisP() implies the conclusion (Q ) Examples: Ifn is odd, the24 ∣ n. Implicit∀n ∈ Z . x ∈ A∪ B ▯ x ∈ A . Implicit∀x ∈ A∪ B Quantifiers are separate from implications. For examp∀x ∈ R,x = y ▯ x = x , the hypothesisx = y . This statement is equivalent∀x ∈ R,(x = y ▯ x = x) The core technique for proving an implication is known as direct proof: 1. Assume the hypothesis. 2. From the hypothesis, deduce the conclusion. The converse of an implicatiP ▯ Q isQ ▯ P . This is very different from the original implication. When we prove a statement and its converse, we have proved P ▯t Q . For an implication with a quantifier, the quantifier is preserved for its converse; t∀x ∈ S,P(x) ▯f Q(x) is∀x ∈ S,Q(x) ▯ P(x) . The converse of "If Bob is a student at uWaterloo, then Bob is a student in Canada" is "If Bob is a student in Canada, Bob is a student at uWaterloo". The contrapositive of an implication P ▯ Q is¬Q ▯ ¬P . This is logically equivalent to the original statement; in other words, P ▯ Q ≡ ¬Q ▯ ¬P . It is occasionally easier to prove the contrapositive rather than the original statement, usually when there are binary choices in the hypothesis and conclusion. The negation of an implication P ▯ Q isP ∧ ¬Q . This is a statement that is true whenever the original statement is true, and false whenever the original statement is true. This can be proven using truth tables. Prove that ∀x ∈ Z,32 ∤ (a + 3)(a + 7) ▯ 2 ∣ a : This is difficult to prove since "not divisible" has few useful properties. We replace the statement with its contrapositive to simplify it. The contrapositive is∀x ∈ Z,2 ∤ a ▯ 32 ∣ (a + 3)(a + 7) . Assume 2 ∤ a. Clearly,a can be written as2k + 1,k ∈ Z . Clearly,(a + 3)(a + 7) is equivalent to(4k + 4k + 4)(4k + 4k + 8) , or16(k + k + 1)(k + k + 2) . 2 2 CLearly, either2 ∣ k + k + 1 or 2 ∣ k + k + 2 . So ∃l ∈ Z,(k + k + 1)(k + k + 2) = 2l . 2 2 Clearly,16(k + k + 1)(k + k 2 2) 2 is equivalent to32l . Clearly,32 ∣ 32l, so32 ∣ (a + 3)(a + 7) . Therefore,∀x ∈ Z,32 ∤ (a + 3)(a + 7) ▯ 2 ∣ a. The inverse of an implication P ▯ Q is¬P ▯ ¬Q . Like the converse, this is also very different from the original implication. Another technique for proving is proof by contradiction: 1. Assume the hypothesis is true. 2. Suppose the conclusion is false. 3. Derive a contradiction, such as1 = 0 . 4. Since the implication cannot be false and result in a contradiction, it is true. To prove A ▯ B , we can prove A ▯ B and B ▯ A . Proof Technique: Induction Full name is "Principle of Mathematical Induction". Useful for proving statements of the form ∀n ∈ N,P(n) , where P(n) is a statement. Also usable for integers greater than 5, -3, or any value. It can also be used for integers less than some value, by proving P(k − 1) rather than P(k + 1) in the inductive conclusion. Prove ∀n ≥ 1,1 + 3 + 5 + ⋯+ (2n− 1) = n 2 : 1. Base case: verify P(1) is true. 2. Inductive hypothesis: assume that P(k) is true for some fixed integek ≥ 1 . 3. (Work towards conclusion) 4. Inductive conclusion: using the inductive assumption, prove thatP(k + 1) . 5. End: therefore, P for an ≥ 1 , by the principle of mathematical induction. We can only assume statements. Base case:P(1) is1 = 1 2, which is true. Inductive hypothesis: assume that, for some fixedk ≥ 1 , P(k) is true. The next term is(2k − 1)+ 2 . Adding this to both sides yields 1 + 3 + 5 + ⋯+ (2k − 1)+ (2k + 1) = k + (2k + 1)2 . 2 2 Clearly,k + (2k + 1) = (k + 1) . 2 So 1 + 3 + 5 + ⋯+ (2k − 1)+ (2k + 1) = (k + 1) . Inductive conclusion: ClearlyP(k + 1) is also true. 2 Therefore, for aln ≥ 1,1 + 3 + 5 + ⋯+ (2n− 1) = n . n(n−1) Prove that ∀n ∈ N , the number of 2-element subsets of the set {1,2,…,n} is 2 : This is true fon = 1 :{1} has no 2-element subsets, and is 1(1−1) = 0 . 2 Assume that for some fixed k ≥ 1 ,P(k) is true. That is, count of subsets{1,2,…,k} is k(k−1). 2 Note that {1,2,…,k + 1} is equivalent to{1,2,…,k} ∪ {k + 1} . Note that the two element subsets of this can be put in two groups: * those that do not contain + 1 , which are the 2-element subsets of1,2,…,k} . * those that do contain + 1 , which are of the form,a,k + 1},1 ≤ a ≤ k . k(k−1) By the inductive hypotheses, we know that the number of subsets belonging to the first group are 2 . We know that the number of subsets belonging to the second group is simply . k(k−1) So the number of subsets of {1,2,…,k + 1} is 2 + k . k +k (k+1)k (k+1)((k+1)−1) Clearly, 2 = 2 , or 2 . n(n−1) Therefore, the number of 2-element subsets of the set1,2,…,n} is 2 for all ≥ 1 . Principle of Mathematical Induction A meta-statement at the basis of proof by induction. It is itself a true statement; an axiom. Let P(n) is a statement that depends onn ,n ∈ N . Let b ∈ Z . Let k ∈ Z,k ≥ b . IfP(b) is true, anP(k) ▯ P(k + 1) , thenP(n) is true. 25/9/13 Prove ∀n ≥ 3,n! > 2 2n−4 using induction: 2(3)−4 Base case: Forn = 1 ,3! > 2 , which is equivalent t6 > 4 , which is true. Inductive hypothesis: Assume that for some fixed integek ≥ 3 ,k! > 2 2k−4 . 2(k+1)−4 Fork + 1 , we want to check i(k + 1)! > 2 . Clearly(k + 1)! > 2 2(k+1)−4 is equivalent tk!(k + 1) > 2 2k+2−4 . Clearlyk!(k + 1) > 2 2k+2−4 is equivalent tk!(k + 1) > 2 2k−4 4. 2k−4 k+1 2k−4 Clearlyk!(k + 1) > 2 4 is equivalent to 4 k! > 2 . Sincek + 1 ≥ 4 , k+1 ≥ 1 , andk+1 k! ≥ k!. 4 4 Since k+1 k! ≥ k! ,k+1 k! > 2 2k−4. 4 4 2(k+1)−4 2k−4 Inductive conclusion: S(k + 1)! > 2 is true k! > 2 . Therefore,∀n ≥ 3,n! > 2 2n−4 , by the principle of mathematical induction. 27/9/13 Strong Induction The induction done to this point is known as simple induction. When this is not possible, there is also strong induction, which is basically the same thing, generalized to work with more base cases. Strong induction is useful for proving statements of the for∀n ≥ 1,P(x) . 1. Base case: verify thP(1)…P(b) are true, for someb ≥ 1 . 2. Inductive Hypothesis: assume thatP(1)…P(k) are true, for somek ≥ b . 3. (Work towards conclusion) 4. Inductive conclusion: thereforP(x) is true for x ≥ 1 , by the principle of strong induction. ;wip: principle of strong induction 5 n−1 Given that fn is the n-th number in the Fibonacci sequence {1,1,2,3,5,…} ), provefn≤ ( 3 : 0 1 ≤ 5 0 Base case: Forn = 1 ,1 ≤ ( 3 , or1 ≤ 1 , which is true. 1 Base case: Forn = 2 ,1 ≤ ( ) , or1 ≤ 5, which is true. 3 3 5 k−1 Inductive hypothesis: Assume that for some integer k ≥ 2 ,fk≤ ( 3 . k For k + 1 , we want to check if k+1 ≤ ( 3 . k k−1 Clearly,f ≤ ( ) is equivalent tof + f ≤ 5 ( ) . k+1 3 k k−1 3 3 5 k−1 Clearly,fk+ f k−1 ≤ ( 3 + f k−1 . ;wip How many cases should be verified (i.e., what is the value ob?)? As a general rule, if the proofP(k + 1) requires that k ≥ x , thenx is the smallest possible value fob. Studying Divisibility Recall that in ∈ Z and m ∈ Z , m ∣ n ▯ ∃k ∈ Z,n = km Transitivity of divisibiilty (TD) Proposition: for integersa,b,c , a ∣ b and b ∣ c, thena ∣ c. Proof: Leta ,b, andc be arbitrary integers. Assume that a ∣ band b ∣ c. This means ∃r ∈ Z,b = ra and ∃s ∈ Z,c = sb . Letk = sr , sok ∈ Z . Clearly,c = sb = s(ra) = (sr)a = ka . So ∃k ∈ Z,c = ka . Since a,b, and c are arbitrary, this is true for all integers. ;wip: read chapter 18 Divisibility of integer combinations (DIC) Proposition: for integersa,b, and c, ia ∣ band a ∣ c, thena ∣ (bx + cy),x ∈ Z,y ∈ Z (a divides every ILC ob and c). ILC: integer linear combination, any integer of the forbx + cy,x ∈ Z,y ∈ Z . Proof: Leta ,b,c be arbitrary integers. We are trying to prove that∀x ∈ Z,∀y ∈ Z,a ∣ (bx + cy) This means ∃r ∈ Z,b = ra and ∃s ∈ Z,c = sb . Assume a ∣ b and a ∣ c. Letx and y be arbitrary integers. Construct k = rx + sy . Clearly,bx + cy = (ra)x + (rs)y = a(rx + sy) = ka . So a ∣ (bx + cy) . Since a,b,c ,x, and y are arbitrary, the statement is true for all integers. Proposition: D plusminus C: for integersa ,b,c,a ∣ (b + c) and a ∣ (b − c) . Proof: Leta ∈ Z,b ∈ Z,c ∈ Z . Assume a ∣ b and a ∣ c. Then a ∣ (bx + cy) for any x ∈ Z,y ∈ Z , by DIC. In particulara ∣ (b + c) ora ∣ (b − c) . Bounds by divisibility (BBD) Proposition: for integersa and b, ia ∣ band b ≠ 0 ,∣a ≤ b∣ ∣. Proof: Leta and b be arbitrary integers. Assume that a ∣ band b ≠ 0 . So ∃k ∈ Z,b = ka . Since,b ≠ 0 and a ≠ 0 ,b ≠ 0 . So k ≥ 1 . Clearly,a ≤ a k = ak = b ∣ ∣ ∣. So a ≤ b . Division Algorithm Ifa and b are integers andb > 0 , then there exisst the unique integqrand rsuch that a = qb + r,0 ≤ r ≤ b . q is the quotientr is the remainder. 30/9/13 GCD Greatest common divisor. Leta ∈ Z,b ∈ Z such thata and b are not both 0. Letd ∈ Z,d ≥ 0 . We can write d = gcd(a,b) , provided all of the following are true: d ∣ a ∧ d ∣ b(d is a common divisor) ∀c ∈ Z , ic ∣ a ∧ c ∣ , thenc ≤ d d is the greatest of all the common divisors). Also,0 = gcd(a,b) , rather than undefined. This is to smooth out certain operations. The GCD is always positive. gcd(8,15) = 1 gcd(−6,−15) = 3 gcd(10,0) = 10 gcd(0,0) = 0 gcd(a,0) = a ∣ ∣ gcd(a,b) = gcd(b,a) Proposition:∀x ∈ Z,gcd(n,n+ 1) = 1 . Proof: We need to prove that d = 1 satisfied = gcd(n,n+ 1) . Letd = 1 . Clearlya ∣ n∧ a ∣ (n+ 1) , so 1 is a common divisor. Letc be an arbitrary integer. Assume that c ∣ nand c ∣ (n+ 1) . So c ∣ ((n+ 1)− n) ,c ∣ . So c = ±1 , andc ≤ d . Therefore,d = 1 satisfies the definition of the GCD, gcd(n,n+ 1) = 1 . Proposition:∀a ∈ Z,∀b ∈ Z,gcd(a,b) = gcd(a,a + b) Proof: We need to prove gcd(a,b) is the GCD of gcd(a,a + b) . Leta and b be arbitrary integers. Letd = gcd(a,b) . So d ∣ a ∧ d ∣ . So d ∣ (a + b) . We need to prove that d is the greatest of the common divisors. Let cbe an arbitrary integer such that c ∣ a ∧ c ∣ (a + b). So c ∣ ((a + b)− a) , andc ∣ b. So ifc ∣ a ∧ c ∣ b c ≤ d . Therefore, d is the GCD of a and a + b . GCD with remainders (GCD-WR) Proposition: for integersa ,b, not both 0, iq and r are integers such that a = qb + r , then gcd(a,b) = gcd(b,r) . The GCD of two numbers is equal to the GCD of the dividend of their quotient and the remainder of their quotient. Proof: Let a ∈ Z,b ∈ Z , such thata and b are not both 0. Assume q ∈ Z,r ∈ Z such that . a = qb + r Let d = gcd(a,b) . We know that d ∣ a and d ∣ b. Since d ∣ (ax + by) d ∣ (a − qb) . We know that a − qb = r , sod ∣ r. So d ∣ b and d ∣ r - d is a common divisor of b and r . Let cbe an arbitrary integer such that c ∣ b ∧ c ∣ r We know that c ∣ (bx + ry) , soc ∣ (bq+ r) . We know that bq+ r = a , soc ∣ a. So ifc ∣ a ∧ c ∣ b c ≤ d . Therefore, d is the GCD of b and r. 2/10/13 Use GCD-WR to compute gcd(322,98) : Let a = 322 ,b = 98 . So q = 3 ,r = 28 . So gcd(322,98) = gcd(98,28) . This is simpler, but if we do it again it could be even simpler. Let a = 98,28 . So q = 3 ,r = 14 . So gcd(98,28) = gcd(28,14) . This is simpler, but if we do it again it could be even simpler. Let a = 28 ,b = 14 . So q = 2 , andr = 0 . So gcd(28,14) = gcd(14,0) = 14 . This is called the Euclidean algorithm. It can be used to calculate the GCD without knowing any of the factors of a or b. General algorithm: 1. Replace the larger number in the GCD with the remainder of dividing it with the other number. 2. Repeat step 1 until the remainder is 0. 3. The non-zero number is the GCD. GCD characterization theorem (GCD-CT) Prosposition: given integers a ,b,d , id > 0 ,d ∣ a ∧ d ∣ b , andd = ax + by,x ∈ Z,y ∈ Z ,d = gcd(a,b) . In other words, if a positive integer is a common divisor ofa and b and is a linear combination of them, then it is the GCD of a and b. Use GCD-CT to verify 14 = gcd(322,98) : Let a = 322 ,b = 98 . Let x = −3 ,y = 10 . Let d = 14 . Clearly,d > 0,d ∣ a,d ∣ b. Clearly,d = ax + by . So d = gcd(a,b) . This theorem does not tell us how to fxnand y , or if they even exist. Proof: Let a,b,d be arbitrary integers. Let x,y be arbitrary integers. Let d ∈ Z,d > 0 . Assume d ∣ a ∧ d ∣ b,d = ax + by . Let c ∈ Z be an arbitrary common divisor oa and b. Then c ∣ (ax + by) , by DIC. So c ∣ d. Since d ≠ 0 ,∣c ≤ d∣ ∣, anc ≤ d , by BBD. So d = gcd(a,b) . Extended Euclidean Algorithm (EEA) Proposition: given integeasand b, we can compute gcd(a,b) , and there exist at least one pair of ixteandy such that ax + by = gcd(a,b) . Proof: ;wip There are often multiple possible valuesxoand y that can result in a linear combination. EEA Table: technique for findigcd(a,b) and integersx and y such thatax + by = gcd(a,b) all at the same time. EEA works with positive inputs only. However, sincegcd(a,b) = gcd( a , b ) ∣, we can simply work wit∣a∣and ∣b∣and proceed with the algorithm. Then, x\sgn(a) and y\sgn(b) are the solutions to the original equation. We start by constructing a table, always with the same initial configuration: x y r q 1 0 a 0 0 1 b 0 Then, we construct the rows after them with their recursive definitions: q 1 0 q = 0 2 rn−2 qn= ⌊ r ⌋ n−1 rn= r n−2 − q nr n−1 xn= x n−2 − qn⋅x n−1 y = y − q ⋅y n n−2 n n−1 We stop when r_n = 0. The value or in the row before this is the GCD. Note thatax n by = n n . So the last nonzero remainder has correspondixgand y values that are coefficients for a linear combination oa and b equal to it. In other words,xtand y values in that row are a certificate of correctness for the GCD. For example, findingcd(42042,1071) : x y r q 1 0 42042 0 0 1 1071 0 1 -39 273 39 -3 118 252 3 4 -157 21 1 - - 0 12 We stop here since the remainder is 0. Now we can read the x,y, andr = gcd(42042,1071) from the next-to- last row. Sincegcd(a,b) = gcd(b,a) , we can save a few steps by swapping the two if the second value is greater, so the bigger value is always in the first row. Certificates of Correctness IfP(n) is a statement dependingnoa ∈ Z , then some daDa and knowledgeK give a certificate of correctness of P(a) if some easy calculations Diand aand K proveP(a) . Example:P(529) : "529 is a perfect square" Certificate of correct23 = 529 Explanation: this proves the statement with only simple operations. Example:P(1147) : "1147 is not prime" Certificate of correct37 ⋅31 = 1147 Explanation: this proves the statement with only simple operations. Example:P(1,379,421) :1 = gcd(379,421) Certificate of correct1 = 10 ⋅379 − 9 ⋅421 Explanation: given 1 > 0 ,1 ∣ 379 ∧ 1 ∣ 42, and 1 is an integer linear combination of 379 and 421, 1 is the GCD by GCD-CT. 4/10/13 How did we find the numbers used in the GCD-CT certificate of correctness above? Consider42042x + 1071y = gcd(42042,1071) = 21 . How do we fixdandy ? Consider the GCD calculated with GCD-WR: 42042 = 39 ⋅1071 + 273 gcd(42042,1071) = gcd(1071,273) 1071 = 3 ⋅273 + 252 gcd(1071,273) = gcd(273,252) 273 = 1 ⋅252 + 21 gcd(273,252) = gcd(252,21) 252 = 12 ⋅21 + 0 gcd(252,21) = gcd(21,0) = 21 Write the last value as a linear combination of the previous21 = 273 − 1 ⋅252 . Rewrite term:21 = 273 − 1 ⋅(1071 − 3 ⋅273) . Expand and simplify21 = 4 ⋅273 − 1071 . Rewrite term:21 = 4cdot(42042 − 39 ⋅1071)− 1071 . Expand and simplify4 ⋅42042 − 157 ⋅1071 . Clearlyx = 4,y = −157 . Clearly4 ⋅42042 − 157 ⋅1071 = 21 , and 7/10/13 Summary Consider ∀x,P(x) ▯ Q(x) . This is not a simple implication due to the quantifier. However, it still acts like an implication. The hypothesis isP(x) . The conclusion isQ(x) . The converse is∀x,Q(x) ▯ P(x) . The contrapositive i∀x,¬Q(x) ▯ ¬P(x) . The negation is¬(∀x,P(x) ▯ Q(x)) , or in simplified f∃x,P ∧ ¬Q(x) . x < y < z is equivalent x < y∧ y < z . So the negation x ≥ y∨ y ≥ z . A statement of the for(P ∧ ¬Q) ▯ ¬R is generally proven using the contrapositR ▯ ( (P ▯ Q) , assume R and P , proveQ ), or by contradiction (sup(P ∧ ¬Q) and R , then reach an impossible condition). n 1 Prove via induction that = 1 − 2n for integern ≥ 1 : i=1 Base case: clearly,= 1 − 1. 2 2 k Inductive hypothesis: Lk ≥ 1. Assume ∑ = 1 − 1 . i=1 2k 1 ClearlyLHS k+1 = LHS +k 2k+1 By the inductive hypothesRHS = RHS + 1 . k+1 k 2k+1 So RHS k+1 = 1 − 1 + 1 . 1k 1 2k+1 1 So RHS k+1 = 1 − 2 k, andRHS k+1 = 1 − k+1. 2 k 2 k+1 1 1 Inductive conclusion: Clearly, = 1 − 2k, then = 1 − 2k+1. n i=1 i=1 Therefore,∑ = 1 − 1, by the POMI. i=1 2n 9/10/13 GCD-CT says that if a certificate of a GCD exists, the GCD exists. EEA says that if a GCD exists, a certificate of its correctness exists. So for any GCD, we can have a certificate verifying its correctness. EEA is the converse of GCD-CT. Coprimality Two integers a and b are coprime ifgcd(a,b) = 1 - if they have no common factors other than 1 and -1. For example, 4 and 9 are coprime. 11/10/13 Coprimeness and Divisibility (CAD) Proposition: for any integera,b,d , id ∣ aband gcd(d,a) = 1 , thena ∣ b. Proof: Leta,b,d be arbitrary integers. Assume d ∣ aband gcd(d,a) = 1 . We want to prove d ∣ b. By EEA,∃x,y ∈ Z,dx + ay = 1 . Clearly, this is equivalb(dx + ay) = b . Clearly, this is equivalend(bx)+ (ab)y = b . Clearlyd ∣ d, andd ∣ ab. By DIC,d divides every integer linear combination od and ab. So d ∣ (d(bx)+ (ab)y) . So d ∣ . Proof by elimination To prove a statement of the formP ∨ Q , we assume ¬Q and from that prove Q . This is based on the observation thaP ∨ Q ≡ ¬(¬P)∨ Q ≡ ¬P ▯ Q . Primality An integer p > 1 is prime if an only if its only positive divisors arep1.and Negative numbers, 0, and 1 cannot be prime. Lemma: given integers p ,a, ip is prime andp ∤ a, thengcd(p,a) = 1 . In other words, a prime that does not divide a number is coprime to it. Proof: Assume p is prime andp ∤ a. Clearly, the divisorspoare −p,−1,1,p . Clearly, the divisorsaoinclude -1 and 1. Sincep ∤ a,a ≠ p . So the only possible common divisors are -1 and 1. So gcd(p,a) = 1 . Primes and Divisibility (PAD) Commonly known as Euclid's Lemma. Corollary: given integerp,a,b , ip is prime andp ∣ ab, thenp ∣ a ∨ p ∣ . Letp,a,b be arbitrary integers. Proof by elimination. Assume p is prime andp ∣ ab. Assume p ∤ a. By the previous lemma, since p is prime and p ∤ a,gcd(p,a) = 1 . By CAD, since p ∣ ab and gcd(p,a) = 1 p ∣,b . GCD of One (GCD OO) Proposition: given integers a,b, if there are integerx,y such thatax + by = 1 , thengcd(a,b) = 1 . Proof: Clearly,1 > 0,1 ∣ a,1 ∣ b . By GCD-CT, ax + by = 1 implies gcd(a,b) = 1 . By EEA, the proposition's converse is also true. So we can write the following: Proposition: given integers a,b gcd(a,b) = 1 if and only if there are integerx,y such that ax + by = 1 . Division by the GCD (DB GCD) Proposition: given integers a,b, igcd(a,b) = d,d ≠ 0 , thengcd( , ) = 1 d d Proof: By EEA, there are integersx,y such that ax + by = d . Since a and b are integers, ax + b y = d . a d b d d d d So d x + d y = 1 . a b By GCD-OO, gcd( ,d) d 1 . Linear Diophantine Equations (LDE) A linear equation in the style of Diophantus, a Greek mathemetician who invented a theory of the integers. They are equations having integer solutions only. 16/10/13 A linear Diophantine equation in two variables is any equation of the form ax + by = c , witha,b,c ∈ Z , and we seek x,y ∈ Z . In other words, we seek only integer solutions. 2x + 3y = 4 - solutions includex = 2,y = 0 and x = −1,y = 2 . 6x + 9y = 10 - no solutions These equations will have either infinitely many solutions, or no solutions. Linear Diophantine equation theorem, part 1 (LDET 1) Proposition: given integers a,b,c ∈ Z ,d = gcd(a,b) , the linear Diophantine equationax + by = c has solutions if and only ifd ∣ c. Proof: We want to show that ax + by = c having solutions in Z ▯ d ∣ c. First we will prove thaax + by = c having solutions in Z ▯ d ∣ c. Assume ax + by = c has solutions inZ . So ∃x,y ∈ Z,ax + by = c (thex and y here are no longer variables, and are specific integers). We know that d = gcd(a,b) . So d ∣ a and d ∣ b. By DIC, d ∣ (au + bv),u,v ∈ Z . So d ∣ (ax + by) , and sod ∣ c. Now we will prove the converse, that d ∣ c ▯ ax + by = c has solutions inZ . Assume d ∣ c . So ∃k ∈ Z,c = kd . By EEA, ∃x,y ∈ Z,d = ax + by . So kd = a(kx)+ b(ky) = c . So kx and ky are integer solutions to the equation. So the equation must have solutions inZ . Since the implication and its converse are true, + by = c having solutions inZ ▯ d ∣ c. The proof in the backwards direction shows us how to find at least one solution to the equation. Find one solution to the LDE21x + 15y = 12 : Clearlya = 21,b = 15,c = 12,d = gcd(21,15) = 3 . Since d ∣ , there are solutions to the equation. Using EEA, we find thatd = −2a + 3b . We know that c = kd,k ∈ Z . Specifically12 = 4 ⋅3 , sok = 4 . Clearly,k)d = −2ka + (3k)b = c . So 12 = (−2 ⋅4)a + (3 ⋅4)b = −8a + 12b . So x = −8,y = 12 is a solution to the LDE. Linear Diophantine equation theorem, part 2 (LDET 2) Proposition: given integersa,b,c ab ≠ 0 d = gcd(a,b) , if the LDax + by = c and x0,y 0 is one particular integer solution, then the complete integer solution is x = x0 + b k,y = y 0− a k,k ∈ Z . d d b a So ax + by = c ▯ x = x 0 d n,y = y −0 d . So the solutions to an LDE, if they exist, are integer multiples of a at
More Less

Related notes for MATH 135

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit