Question? Leave a message!




Lecture notes in Discrete Structures

lecture notes on algebraic structures in discrete mathematics and lecture notes discrete mathematics and its applications pdf free download
DanialOrton Profile Pic
DanialOrton,Hawaii,Professional
Published Date:09-07-2017
Your Website URL(Optional)
Comment
A Course in Discrete Structures Rafael Pass Wei-Lung Dustin TsengPreface Discrete mathematics deals with objects that come in discrete bundles, e.g., 1 or 2 babies. In contrast, continuous mathematics deals with objects that vary continuously, e.g., 3.42 inches from a wall. Think of digital watches versus analog watches (ones where the second hand loops around continuously without stopping). Why study discrete mathematics in computer science? It does not directly help us write programs. At the same time, it is the mathematics underlying almost all of computer science. Here are a few examples:  Designing high-speed networks and message routing paths.  Finding good algorithms for sorting.  Performing web searches.  Analysing algorithms for correctness and eciency.  Formalizing security requirements.  Designing cryptographic protocols. Discrete mathematics uses a range of techniques, some of which is sel- dom found in its continuous counterpart. This course will roughly cover the following topics and speci c applications in computer science. 1. Sets, functions and relations 2. Proof techniques and induction 3. Number theory a) The math behind the RSA Crypto system 4. Counting and combinatorics 5. Probability a) Spam detection b) Formal security 6. Logic a) Proofs of program correctness 7. Graph theory ia) Message Routing b) Social networks 8. Finite automata and regular languages a) Compilers In the end, we will learn to write precise mathematical statements that captures what we want in each application, and learn to prove things about these statements. For example, how will we formalize the infamous zero- knowledge property? How do we state, in mathematical terms, that a banking protocol allows a user to prove that she knows her password, without ever revealing the password itself?Contents Contents iii 1 Sets, Functions and Relations 1 1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Set Cardinality, revisited . . . . . . . . . . . . . . . . . . . . . . 8 2 Proofs and Induction 13 2.1 Basic Proof Techniques . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Proof by Cases and Examples . . . . . . . . . . . . . . . . . . . 15 2.3 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Inductive De nitions . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5 Fun Tidbits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3 Number Theory 37 3.1 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4 The Euler  Function . . . . . . . . . . . . . . . . . . . . . . . 52 3.5 Public-Key Cryptosystems and RSA . . . . . . . . . . . . . . . 56 4 Counting 61 4.1 The Product and Sum Rules . . . . . . . . . . . . . . . . . . . 61 4.2 Permutations and Combinations . . . . . . . . . . . . . . . . . 63 4.3 Combinatorial Identities . . . . . . . . . . . . . . . . . . . . . . 65 4.4 Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . . . . 69 4.5 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . 72 5 Probability 73 iii5.1 Probability Spaces . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2 Conditional Probability and Independence . . . . . . . . . . . . 77 5.3 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.4 Expectatation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.5 Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6 Logic 95 6.1 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.2 Logical Inference . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3 First Order Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 7 Graphs 109 7.1 Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . 112 7.2 Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.3 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7.4 Random Graphs Optional . . . . . . . . . . . . . . . . . . . . 122 8 Finite Automata 125 8.1 Deterministic Finite Automata . . . . . . . . . . . . . . . . . . 125 8.2 Non-Deterministic Finite Automata . . . . . . . . . . . . . . . 130 8.3 Regular Expressions and Kleene's Theorem . . . . . . . . . . . 133 A Problem Sets 137 A.1 Problem Set A . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 B Solutions to Problem Sets 141 B.1 Problem Set A . . . . . . . . . . . . . . . . . . . . . . . . . . . 141Chapter 1 Sets, Functions and Relations \A happy person is not a person in a certain set of circumstances, but rather a person with a certain set of attitudes." Hugh Downs 1.1 Sets A set is one of the most fundamental object in mathematics. De nition 1.1 (Set, informal). A set is an unordered collections of objects. Our de nition is informal because we do not de ne what a \collection" is; a deeper study of sets is out of the scope of this course. Example 1.2. The following notations all refer to the same set: f1; 2g;f2; 1g;f1; 2; 1; 2g;fxjx is an integer; 1x 2g The last example read as \the set of all x such thatx is an integer between 1 and 2 (inclusive)". We will encounter the following sets and notations throughout the course: ; =fg, the empty set.  N =f0; 1; 2; 3;:::g, the non-negative integers +  N =f1; 2; 3;:::g, the positive integers  Z =f:::;2;1; 0; 1; 2:::g, the integers  Q =fqjq =a=b; a;b2Z; b =6 0g, the rational numbers +  Q =fqjq2Q; q 0g, the positive rationals  R, the real numbers 12 sets, functions and relations +  R , the positive reals Given a collection of objects (a set), we may want to know how large is the collection: De nition 1.3 (Set cardinality). The cardinality of a setA is the number of (distinct) objects in A, written asjAj. WhenjAj2N (a nite integer), A is a nite set; otherwise A is an in nite set. We discuss the cardinality of in nite sets later. Example 1.4.jf1; 2; 3gj =jf1; 2;f1; 2ggj = 3. Given two collections of objects (two sets), we may want to know if they are equal, or if one collection contains the other. These notions are formalized as set equality and subsets: De nition 1.5 (Set equality). Two setsS andT are equal, written asS =T , ifS andT contains exactly the same elements, i.e., for everyx,x2Sx2T . De nition 1.6 (Subsets). A set S is a subset of set T , written as ST , if every element in S is also in T, i.e., for every x, x2 S x2 T . Set S is a strict subset of T, written as S T if S T , and there exist some element x2T such that x2= S. Example 1.7. f1; 2gf1; 2; 3g. f1; 2gf1; 2; 3g. f1; 2; 3gf1; 2; 3g. f1; 2; 3g6f1; 2; 3g.  For any set S,;S.  For every set S6=;,;S.  ST and TS if and only if S =T . Finally, it is time to formalize operations on sets. Given two collection of objects, we may want to merge the collections (set union), identify the objects in common (set intersection), or identify the objects unique to one collection (set di erence). We may also be interested in knowing all possible ways of picking one object from each collection (Cartesian product), or all possible ways of picking some objects from just one of the collections (power set). De nition 1.8 (Set operations). Given setsS andT , we de ne the following operations:1.1. SETS 3  Power Sets.P(S) is the set of all subsets of S.  Cartesian Product. ST =f(s;t)js2S;t2Tg.  Union. ST =fxjx2S or x2Tg, set of elements in S or T .  Intersection. S\T =fxjx2S, x2Tg, set of elements in S and T .  Di erence. ST =fxjx2S, x2= Tg, set of elements in S but not T .  Complements. S =fxj x2= Sg, set of elements not in S. This is only meaningful when we have an implicit universeU of objects, i.e., S =fxjx2U;x2= Sg. Example 1.9. Let S =f1; 2; 3g, T =f3; 4g, V =fa;bg. Then: P(T ) =f;;f3g;f4g;f3; 4gg.  SV =f(1;a); (1;b); (2;a); (2;b); (3;a); (3;b)g.  ST =f1; 2; 3; 4g.  S\T =f3g.  ST =f1; 2g.  If we are dealing with the set of all integers,S =f:::;2;1; 0; 4; 5;:::g. Some set operations can be visualized using Venn diagrams. See Figure 1.1. To give an example of working with these set operations, consider the following set identity. Theorem 1.10. For all sets S and T , S = (S\T ) (ST ). Proof. We can visualize the set identity using Venn diagrams (see Figure 1.1b and 1.1c). To formally prove the identity, we will show both of the following: S (S\T ) (ST ) (1.1) (S\T ) (ST )S (1.2) To prove (1.1), consider any element x2S. Either x2T or x2= T .  If x2T , then x2S\T , and thus also x2 (S\T ) (ST ).  If x2= T , then x2 (ST ), and thus again x2 (S\T ) (ST ). To prove (1.2), consider any x2 (S\T ) (ST ). Either x2 S\T or x2ST  If x2S\T , then x2S4 sets, functions and relations U U S T S T (a) ST (b) S\T U U S T S T (c) ST (d) S V S T (e) Venn diagram with three sets. Figure 1.1: Venn diagrams of sets S, T , and V under universeU.  If x2ST , then x2S.  In computer science, we frequently use the following additional notation (these notation can be viewed as short hands): De nition 1.11. Given a set S and a natural number n2N, n  S is the set of lengthn \strings" (equivalentlyn-tuples) with alphabet S. Formally we de ne it as the product of n copies of S (i.e., SS S).   S is the set of nite length \strings" with alphabet S. Formally we 0 1 2 0 de ne it as the union of S S S  , where S is a set that contains only one element: the empty string (or the empty tuple \()").1.2. RELATIONS 5  n is the setf0; 1;:::;n 1g. n  Commonly seen set includesf0; 1g as the set ofn-bit strings, andf0; 1g as the set of nite length bit strings. Also observe thatjnj =n. Before we end this section, let us revisit our informal de nition of sets: an unordered \collection" of objects. In 1901, Russel came up with the following 1 \set", known as Russel's paradox : S =fxjx2= xg That is, S is the set of all sets that don't contain themselves as an element. This might seem like a natural \collection", but is S2 S? It's not hard to see that S 2 S S 2= S. The conclusion today is that S is not a good \collection" of objects; it is not a set. So how will know iffxjx satis es some conditiong is a set? Formally, sets can be de ned axiomatically, where only collections constructed from a careful list of rules are considered sets. This is outside the scope of this course. We will take a short cut, and restrict our attention to a well-behaved universe. Let E be all the objects that we are interested in (numbers, letters, etc.), and letU = EP(E)P(P(E)), i.e.,E, subsets ofE and subsets of subsets ofE. In fact, we may extendU with three power set operations, or indeed any nite number of power set operations. Then, S =fxj x2U and some condition holdsg is always a set. 1.2 Relations De nition 1.12 (Relations). A relation on setsS andT is a subset ofST . A relation on a single set S is a subset of SS. Example 1.13. \Taller-than" is a relation on people; (A;B)2 "Taller-than" if person A is taller than person B. \" is a relation on R; \"=f(x;y)j x;y2R; xyg. De nition 1.14 (Re exitivity, symmetry, and transitivity). A relationR on set S is:  Re exive if (x;x)2R for all x2S.  Symmetric if whenever (x;y)2R, (y;x)2R. 1 A folklore version of this paradox concerns itself with barbers. Suppose in a town, the only barber shaves all and only those men in town who do not shave themselves. This seems perfectly reasonable, until we ask: Does the barber shave himself?6 sets, functions and relations  Transitive if whenever (x;y); (y;z)2R, then (x;z)2R Example 1.15.  \" is re exive, but \" is not.  \sibling-of" is symmetric, but \" and \sister-of" is not.  \sibling-of", \", and \" are all transitive, but \parent-of" is not (\ancestor-of" is transitive, however). De nition 1.16 (Graph of relations). The graph of a relationR overS is an directed graph with nodes corresponding to elements of S. There is an edge from node x to y if and only if (x;y)2R. See Figure 1.2. Theorem 1.17. Let R be a relation over S.  R is re exive i its graph has a self-loop on every node.  R is symmetric i in its graph, every edge goes both ways.  R is transitive i in its graph, for any three nodes x, y and z such that there is an edge from x to y and from y to z, there exist an edge from x to z.  More naturally, R is transitive i in its graph, whenever there is a path from node x to node y, there is also a direct edge from x to y. Proof. The proofs of the rst three parts follow directly from the de nitions. The proof of the last bullet relies on induction; we will revisit it later.  De nition 1.18 (Transitive closure). The transitive closure of a relation R   is the least (i.e., smallest) transitive relation R such that RR .  Pictorially, R is the connectivity relation: if there is a path from x to y  in the graph of R, then (x;y)2R . Example 1.19. Let R =f(1; 2); (2; 3); (1; 4)g be a relation (say on set Z).   Then (1; 3)2R (since (1; 2); (2; 3)2R), but (2; 4)2= R . See Figure 1.2.  Theorem 1.20. A relation R is transitive i R =R . De nition 1.21 (Equivalence relations). A relationR on setS is an equiva- lence relation if it is re exive, symmetric and transitive. Equivalence relations capture the every day notion of \being the same" or \equal".1.3. FUNCTIONS 7 2 2 1 3 1 3 4 4  (a) The relation R =f(1; 2); (2; 3); (1; 4)g(b) The relation R , transitive closure of R Figure 1.2: The graph of a relation and its transitive closure. Example 1.22. The following are equivalence relations:  Equality, \=", a relation on numbers (sayN orR).  Parity =f(x;y)j x;y are both even or both oddg, a relation on inte- gers. 1.3 Functions De nition 1.23. A function f :ST is a \mapping" from elements in set S to elements in setT . Formally,f is a relation onS andT such that for each s2S, there exists a unique t2T such that (s;t)2R. S is the domain of f, and T is the range of f.fyjy =f(x) for some x2Sg is the image of f. We often think of a function as being characterized by an algebraic formula, e.g., y = 3x 2 characterizes the function f(x) = 3x 2. Not all formulas 2 2 characterizes a function, e.g. x + y = 1 is a relation (a circle) that is not a function (no unique y for each x). Some functions are also not easily characterized by an algebraic expression, e.g., the function mapping past dates to recorded weather. De nition 1.24 (Injection). f :ST is injective (one-to-one) if for every t2 T , there exists at most one s2 S such that f(s) = t, Equivalently, f is injective if whenever s6=s, we have f(s)6=f(s). Example 1.25.  f :NN, f(x) = 2x is injective.8 sets, functions and relations + + 2  f :R R , f(x) =x is injective. 2 2 2  f :RR, f(x) =x is not injective since (x) =x . De nition 1.26 (Surjection). f :ST is surjective (onto) if the image of f equals its range. Equivalently, for every t2T , there exists somes2S such that f(s) =t. Example 1.27.  f :NN, f(x) = 2x is not surjective. + + 2  f :R R , f(x) =x is surjective. 2  f :RR,f(x) =x is not injective since negative reals don't have real square roots. De nition 1.28 (Bijection). f : S T is bijective, or a one-to-one corre- spondence, if it is injective and surjective. See Figure 1.3 for an illustration of injections, surjections, and bijections. De nition 1.29 (Inverse relation). Given a function f :ST , the inverse 1 1 relation f on T and S is de ned by (t;s)2f if and only if f(s) =t. 1 Iff is bijective, thenf is a function (unique inverse for eacht). Similarly, 1 1 iff is injective, thenf is a also function if we restrict the domain off to be the image off. Often an easy way to show that a function is one-to-one is 1 to exhibit such an inverse mapping. In both these cases, f (f(x)) =x. 1.4 Set Cardinality, revisited Bijections are very useful for showing that two sets have the same number of elements. If f : S T is a bijection and S and T are nite sets, then jSj =jTj. In fact, we will extend this de nition to in nite sets as well. De nition 1.30 (Set cardinality). Let S and T be two potentially in nite sets. S and T have the same cardinality, written asjSj =jTj, if there exists 0 a bijection f :ST (equivalently, if there exists a bijection f :TS). T has cardinality at larger or equal to S, written asjSjjTj, if there exists an 0 injection g :ST (equivalently, if there exists a surjection g :TS). To \intuitively justify" De nition 1.30, see Figure 1.3. The next theorem shows that this de nition of cardinality corresponds well with our intuition for size: if both sets are at least as large as the other, then they have the same cardinality.1.4. SET CARDINALITY, REVISITED 9 X Y X Y (a) An injective function from X to(b) A surjective function from X to Y . Y . X Y (c) A bijective function from X toY . Figure 1.3: Injective, surjective and bijective functions. Theorem 1.31 (Cantor-Bernstein-Schroeder). IfjSjjTj andjTjjSj, thenjSj =jTj. In other words, given injective maps,g :ST andh :TS, we can construct a bijection f :ST . We omit the proof of Theorem 1.31; interested readers can easily nd multiple avours of proofs online. Set cardinality is much more interesting when the sets are in nite. The cardinality of the natural numbers is extra special, since you can \count" the numbers. (It is also the \smallest in nite set", a notion that is outside the scope of this course.) De nition 1.32. A setS is countable if it is nite or has the same cardinality + + asN . Equivalently, S is countable ifjSjjN j. Example 1.33. f1; 2; 3g is countable because it is nite. +  N is countable because it has the same cardinality as N ; consider f : + N N, f(x) =x 1.10 sets, functions and relations  The set of positive even numbers, S =f2; 4;:::g, is countable consider + f :N S, f(x) = 2x. + Theorem 1.34. The set of positive rational numbers Q are countable. + + Proof. Q is clearly not nite, so we need a way to count Q . Note that double counting, triple counting, even counting some element in nite many + times is okay, as long as we eventually count all of Q . I.e., we implicitly + + construct a surjection f :N Q . Let us count in the following way. We rst order the rational numbers p=q by the value of p +q; then we break ties by ordering according to p. The ordering then looks like this:  First group (p +q = 2): 1/1  Second group (p +q = 3): 1/2, 2/1  Third group (p +q = 4): 1/3, 2/2, 3/1 Implicitly, we have f(1) = 1=1, f(2) = 1=2, f(3) = 2=1, etc. Clearly, f is a surjection. See Figure 1.4 for an illustration of f.  ::: 1=1 1=2 1=3 1=4 1=5 ::: 2=1 2=2 2=3 2=4 2=5 ::: 3=1 3=2 3=3 3=4 3=5 ::: 4=1 4=2 4=3 4=4 4=5 ::: 5=1 5=2 5=3 5=4 5=5 . . . . . . . . . . . . . . . Figure 1.4: An in nite table containing all positive rational numbers (with repetition). The red arrow represents how f traverses this tablehow we count the rationals. Theorem 1.35. There exists sets that are not countable. Proof. Here we use Cantor's diagonlization argument. Let S be the set of in nite sequences (d ;d ;::: ) over digitsf0; 1g. Clearly S is in nite. To 1 21.4. SET CARDINALITY, REVISITED 11 + show that there cannot be a bijection withN , we proceed by contradiction. + Supposef :N S is a bijection. We can then enumerate these strings using f, producing a 2-dimensional table of digits: 1 1 1 1 f(1) =s = (d ;d ;d ;::: ) 1 2 3 2 2 2 2 f(2) =s = (d ;d ;d ;::: ) 1 2 3 3 3 3 3 f(3) =s = (d ;d ;d ;::: ) 1 2 3  1 2 3 Now considers = (1d ; 1d ; 1d ;::: ), i.e., we are taking the diagonal 1 2 3  of the above table, and ipping all the digits. Then for any n, s is di erent n th from s in the n digit. This contradicts the fact that f is a bijection.  Theorem 1.36. The real interval 0; 1 (the set of real numbers between 0 and 1, inclusive) is uncountable. Proof. We will show thatj0; 1jjSj, where S is the same set as in the proof of Theorem 1.35. Treat each s = (d ;d ;::: )2 S as the real number 1 2 between 0 and 1 with the binary expansion 0:d d  . Note that this does 1 2 not establish a bijection; some real numbers have two binary expansions, e.g., 2 0:1 = 0:0111 (similarly, in decimal expansion, we have 0:1 = 0:0999 ). We may overcome this \annoyance" in two ways:  Since each real number can have at most two decimal representations (most only have one), we can easily extend the above argument to show thatjSjj0; 2j (i.e., map 0; 1 to one representation, and 1; 2 to the other). It remains to show thatj0; 1j =j0; 2j (can you think of a bijection here?).  We may repeat Cantor's diagonlization argument as in the proof of The-  orem 1.35, in decimal expansion. When we constructs , avoid using the digits 9 and 0 (e.g., use only the digits 4 and 5).  A major open problem in mathematics (it was one of Hilbert's 23 famous problems listed 1900) was whether there exists some set whose cardinality is betweenN andR (can you show thatR has the same cardinality as 0; 1?). Here is a naive candidate:P(N). Unfortunately,P(N) has the same cardi- nality as 0; 1. Note that every elementS2P(N) corresponds to an in nitely th long sequence over digitsf0; 1g (the n digit is 1 if and only if the number n2S). Again, we arrive at the set S in the proof of Theorem 1.35. 2 For a proof, consider letting x = 0:0999 , and observe that 10xx = 0:999 0:0999 = 0:9, which solves to x = 0:1.12 sets, functions and relations The Continuum Hypothesis states that no such set exists. G odel and Cohen together showed (in 1940 and 1963) that this can neither be proved nor disproved using the standard axioms underlying mathematics (we will talk more about axioms when we get to logic).Chapter 2 Proofs and Induction \Pics or it didn't happen." the internet There are many forms of mathematical proofs. In this chapter we introduce several basic types of proofs, with special emphasis on a technique called induction that is invaluable to the study of discrete math. 2.1 Basic Proof Techniques In this section we consider the following general task: given a premiseX, how do we show that a conclusion Y holds? One way is to give a direct proof. Start with premiseX, and directly deduceY through a series of logical steps. See Claim 2.1 for an example. 2 Claim 2.1. Let n be an integer. If n is even, then n is even. If n is odd, 2 then n is odd. Direct proof. If n is even, then n = 2k for an integer k, and 2 2 2 2 n = (2k) = 4k = 2 (2k ), which is even. If n is odd, then n = 2k + 1 for an integer k, and 2 2 2 2 n = (2k + 1) = 4k + 4k + 1 = 2 (2k + 2k) + 1, which is odd.  There are also several forms of indirect proofs. A proof by contrapos- itive starts by assuming that the conclusion Y is false, and deduce that the premise X must also be false through a series of logical steps. See Claim 2.2 for an example. 1314 proofs and induction 2 Claim 2.2. Let n be an integer. If n is even, then n is even. 2 Proof by contrapositive. Suppose that n is not even. Then by Claim 2.1, n is not even as well. (Yes, the proof ends here.)  A proof by contradiction, on the other hand, assumes both that the premise X is true and the conclusion Y is false, and reach a logical fallacy. We give another proof of Claim 2.2 as example. 2 Proof by contradiction. Suppose that n is even, but n is odd. Applying 2 2 Claim 2.1, we see that n must be odd. But n cannot be both odd and even  In their simplest forms, it may seems that a direct proof, a proof by con- trapositive, and a proof and contradiction may just be restatements of each other; indeed, one can always phrase a direct proof or a proof by contrapositive as a proof by contradiction (can you see how?). In more complicated proofs, however, choosing the \right" proof technique sometimes simplify or improve the aesthetics of a proof. Below is an interesting use of proof by contradiction. p Theorem 2.3. 2 is irrational. p Proof by contradiction. Assume for contradiction that 2 is rational. Then p there exists integers p and q, with no common divisors, such that 2 = p=q (i.e., the reduced fraction). Squaring both sides, we have: 2 p 2 2 2 = ) 2q =p 2 q 2 This meansp is even, and by Claim 2.2p is even as well. Let us replacep by 2k. The expression becomes: 2 2 2 2 2 2q = (2k) = 4k ) q = 2k 2 This time, we conclude thatq is even, and soq is even as well. But this leads to a contradiction, since p and q now shares a common factor of 2.  We end the section with the (simplest form of the) AM-GM inequality. Theorem 2.4 (Simple AM-GM inequality). Letx andy be non-negative reals. Then, x +y p  xy 22.2. PROOF BY CASES AND EXAMPLES 15 Proof by contradiction. Assume for contradiction that x +y p xy 2 1 2 ) (x +y) xy squaring non-negative values 4 2 2 ) x + 2xy +y 4xy 2 2 ) x 2xy +y 0 2 ) (xy) 0 But this is a contradiction since squares are always non-negative.  Note that the proof Theorem 2.4 can be easily turned into a direct proof; the proof of Theorem 2.3, on the other hand, cannot. 2.2 Proof by Cases and Examples Sometimes the easiest way to prove a theorem is to split it into several cases. 2 n Claim 2.5. (n + 1)  2 for all integers n satisfying 0n 5. Proof by cases. There are only 6 di erent values of n. Let's try them all: 2 n n (n + 1) 2 0 1  1 1 4  2 2 9  4 3 16  8 4 25  16 5 36  32  2 2 Claim 2.6. For all real x,jxj =jxj . Proof by cases. Split into two cases: x 0 and x 0. 2 2 2  If x 0, thenjxj =x =jxj . 2 2 2 2  If x 0, thenjxj =x = (x) =jxj .  When presenting a proof by cases, make sure that all cases are covered For some theorems, we only need to construct one case that satisfy the theorem statement. 2 n Claim 2.7. Show that there exists some n such that (n + 1)  2 .