Question? Leave a message!




Lecture Notes on Discrete Mathematics

Discrete Mathematics lecture notes pdf free download
ShawnPacinocal Profile Pic
ShawnPacinocal,United States,Researcher
Published Date:09-07-2017
Website URL
Comment
Lecture Notes on Discrete Mathematics A K Lal S Pati November 20, 2016 DRAFT2 General Instructions Throughout this book, an item with a label 2.1.3 means the 3-rd item of the 1-st section of Chapter 2. While defining a new term or a new notation we shall use bold face letters. The symbol := is used at places we are defining a term using equality symbol. A symbol at the end of a statement reminds the reader to verify the statement by writing a proof, if necessary. We assume that the reader is familiar with the very basic of counting. A reader who is not, may avoid the counting items in the initial parts till we start to discuss counting. We also assume that the reader is familiar with some very basic definitions involving sets. Thisbookiswrittenwiththeprimarypurposeofmakingthereaderunderstand the discussion. Wedonotintendtowriteelaborateproofsforthereadertoread,asthereisnoendtoelaboration. Werequestthereadertotakeeachstatementinthebookwiththebestpossiblenaturalmeaning. Here are a few collected quotes, mainly intended to inspire the authors. Albert Einstein • The value of a college education is not the learning of many facts but the training of the mind to think. • Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution. It is, strictly speaking, a real factor in scientific research. • Everything should be made as simple as possible, but no simpler. • Do not worry about your difficulties in Mathematics. I can assure you mine are still greater. DRAFTContents 1 Basic Set Theory 7 1.1 Common Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 More on the Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . 14 1.4 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Advanced Topics in Set Theory 31 2.1 Families of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 More on Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3 More on Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.4 Supplying Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3 Countability, cardinal numbers and partial order 45 3.1 Countable-Uncountable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4 Introduction to Logic 59 4.1 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Predicate Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5 Lattices and Boolean Algebra 79 5.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6 Counting 91 6.1 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.1.1 Multinomial theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.2 Circular Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.3 Solutions in Non-negative Integers . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.4 Set Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.5 Lattice Paths and Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.6 Some Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 3 DRAFT4 CONTENTS 7 Advanced Counting Principles 117 7.1 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.2 Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.3 Generating Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7.4 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 7.5 Generating Function from Recurrence Relation . . . . . . . . . . . . . . . . . . . 138 8 Graphs 147 8.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 8.2 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 8.3 Isomorphism in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 8.5 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 8.6 Eulerian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 8.7 Hamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 8.8 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 8.9 Matching in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 8.10 Ramsey Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 8.11 Degree Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 8.12 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 8.13 Vertex Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 8.14 Adjacency Matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 8.15 More Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Index 188 DRAFTCONTENTS 5 1 1 1 Remained changed to Remainder. 1+ + +···+ is not an integer. 2 3 n DRAFT6 CONTENTS DRAFTChapter 1 Basic Set Theory 1.1 Common Notations The following are some notations we shall follow throughout this document. N : the set of natural numbers N : the setN∪0, called the set of whole numbers 0 Z : the set of integers Q : the set of rational numbers R : the set of real numbers n : the set1,2,...,n c A : the complement of a set A in some set that will be clear from the context P(A) : the power set of A A×B : the cartesian product of A and B ∅ : the empty set pa : the integer p divides the integer a 1.2 Preliminaries We expect the readers to have familiarity with the following definitions. Definition 1.2.1. Let A and B be two sets. 1. Subset of a set If C is a set such that each element of C is also an element of A, then C is said to be a subset of the set A, denoted C⊆A. 2. Equality of sets The sets A and B are said to be equal if A⊆ B and B⊆A, denoted A =B. 3. Cartesian product of sets The cartesian product of A and B, denoted A×B, is the set of all ordered pairs (a,b), where a∈ A and b∈ B. Specifically, A×B =(a,b) a∈ A,b∈B. c 4. Set complement Let C⊆ A. The complement of C in A, denoted C , is a set that c containseveryelementofAthatisnotanelementofC. Specifically,C =x∈Ax6∈C. 7 DRAFT8 CHAPTER 1. BASIC SET THEORY 5. Set union Theunion of A andB, denoted A∪B, is the set that exactly contains all the elements of A and all the elements of B. Specifically, A∪B =xx∈A or x∈B. 6. Set intersection The intersection of A and B, denoted A∩B, is the set that only contains the common elements of A and B. Specifically, A∩B =x x∈A and x∈B. The set A and B are said to be disjoint if A∩B =∅. 7. Set difference Theset difference of A and B, denoted A\B, is a set that contains all those elements of A which are not in B. Specifically, A\B =x∈Ax6∈B. 8. Symmetric difference The symmetric difference of A and B, denoted AΔB, equals (A\B)∪(B\A). Example 1.2.2. Let A=b,c,b,c,b and B =a,b,c. Then 1. A∩B =b, 2. A∪B =a,b,c,b,c,b,c, 3. A\B =b,c,b,c, 4. B\A=a,c, and 5. AΔB =b,c,b,c,a,c. The following are a few well known facts. The readers are supposed to verify them for clarity. Fact 1.2.3. 1. For any set A, we have A⊆A and∅⊆A. 2. If A⊆B then it is not necessary that B⊆A. 3. For any set A and B, the sets A\B, A∩B and B\A are pairwise disjoint. Thus, A∪B is their disjoint union. That is, A∪B = (A\B)∪(A∩B)∪(B\A). (1.1) 4. For any setA andB, thesets A\B andA∩B are disjoint. Thus,A is their disjoint union. That is, A= (A\B)∪(A∩B) (1.2) 5. If B⊆A, then A= (A\B)∪B (follows from (1.2)). 6. AΔB = (A∪B)\(A∩B) (follows from (1.1) and Item 3). Definition 1.2.4. Power set Let A be a set and B⊆ A. Then, the set that contains all subsets of B is called the power set of B, denotedP(A). Example 1.2.5. 1. Let A =∅. Then,P(∅) =∅,A =∅. 2. Let A =∅. Then,P(A) =∅,A =∅,∅. 3. Let A =a,b,c. Then,P(A) =∅,a,b,c,a,b,a,c,b,c,a,b,c. DRAFT1.2. PRELIMINARIES 9 4. LetA =b,c,b,c. Then,P(A) =∅,b,c,b,c,b,c,b,c. Definition 1.2.6. Relation, domain set and codomain set Let A and B be two sets. A relation f from A to B, denoted f : A→ B, is a subset of A×B. The set A is called the domain set and the set B is called the codomain set. Thus, for any sets A and B the sets∅ and A×B are always relations from A to B. Example 1.2.7. Let A = 3, B =a,b,c and f =(1,a),(1,b),(2,c). Then, f :A→B is a 1 relation. We can draw a picture for f. a 1 2 b c 3 f Definition 1.2.8. 1. Domain, range and inverse relation Let f : A→ B be a relation. 2 Then,bythedomainoff wemeanthesetdomf:=a(a,y)∈fandbytherangeof −1 f wemeanthesetrngf:=b (x,b)∈f. Theinverseoff isf :=(y,x) (x,y)∈f. −1 Notice that f is a relation from B to A. For example, the relation f in Example 1.2.7 −1 has domf =1,2, rngf =a,b,c and f =(a,1),(b,1),(c,2). 2. Pre-imageandimage Letf :A→B bearelationand(x,y)∈f. Wecallxapre-image of y and y an image of x. Also, for any set X, we define f(X) :=y(x,y)∈f,x∈X. Thus, f(X)=∅ if X∩A=∅. We write f(x) to mean f(x). We write f(x)=y to mean that f(x)=y. For example, consider the relation f in Example 1.2.7. Then, (a) f(1) =a,b, f(2) =c and f(3) =∅. −1 −1 −1 −1 (b) f (c) = 2, f (b) = 1, f (1) =∅, f (4) =∅. −1 (c) for X =1,4,c, one has f(X) =a,b and f (X) =2. Definition 1.2.9. Single valued relation and function A relation f : A→ B is single valued if f(x) is a singleton, for each a∈ domf. A function f from A to B is a single valued relation such that domf = A. Henceforth, for any function f, we assume that domf =6 ∅. For example, the relation f in Example 1.2.7 is not single valued. However, if we delete (1,a) from f, then it is single valued. Moreover, to make f a function from A to B, we need to add either (3,a), or (3,b), or (3,c). In particular, the relations g =(1,b),(2,c),(3,b) and 1 g =(1,b),(2,c),(3,a) are indeed functions. 2 The following is an immediate consequence of the definition. 1 We use pictures to help our understanding and they are not parts of proof. 2 The domain set is the setfrom which we defineourrelations butdomf is the domain oftheparticular relation f. They are different. DRAFT10 CHAPTER 1. BASIC SET THEORY Proposition 1.2.10. Let f :A→B be a relation and S be any set. Then, 1. f(S)6=∅⇔ dom(f)∩S =6 ∅. −1 2. f (S) =6 ∅⇔ rng(f)∩S6=∅. Proof. We will prove only one way implication. The other way is left for the reader. Part 1: Since f(S)6=∅, one can find a∈ S∩A and b∈ B such that (a,b)∈ f. This, in turn, implies that a∈ dom(f). As a∈S, a∈ dom(f)∩S. Part 2: Since rng(f)∩S6=∅, one can findb∈ rng(f)∩S and a∈A such that (a,b)∈f. This, −1 −1 in turn, implies that a∈f (b)⊆f (S) as b∈S. Definition 1.2.11. One-one/Injection A function f :A→B is called one-one (also called −1 aninjection), iff (b)≤ 1, for each b∈B. Equivalently, f :A→B is one-one iff(x)6=f(y) is true, foreach pairx6=y inA. Equivalently, f is one-one ifx =y is true, for each pairx,y∈A whenever f(x)=f(y). Convention: Let p(x) be a polynomial in x with integer coefficients. Then, by writing ‘f : Z→ Z is a function defined by f(x) = p(x)’, we mean the function f =(a,p(a)) a∈ Z. For 2 2 example, the function f(x) =x stands for the set(a,a )a∈Z. Example 1.2.12. 1. InDefinition1.2.9, thefunctiong isone-onewhereasg isnotone-one. 2 1 2 2. The function f :Z→Z defined by f(x)=x is not one-one. 2 3. The function f :N→N defined by f(x)=x is one-one. 0 4. The function f : 3→a,b,c,d defined by f(1) = c, f(2) = b and f(3) = a, is one-one. Verify that there are 24 one-one functions f :3→a,b,c,d. 5. Let∅ =6 A(B. Then, f(x)=x is a one-one map from A to B. 6. There is no one-one function from the set 3 to its proper subset 2. 7. There are one-one functions f from the setN to its proper subset2,3,.... One of them is given by f(1) = 3, f(2) = 2 and f(n)=n+1, for n≥ 3. Definition 1.2.13. Restriction function Let f : X→ Y be a function and A⊆ X, A =6 ∅. Then, by f we mean the restriction of f to A and denote it byf . That is, f =(x,y) A A A (x,y)∈f,x∈A. Example 1.2.14. Define f :R→R as f(x) = 1 if x is irrational and f(x) = 0 if x is rational. Then, f :Q→R is the constant 0 function. That is, f (x) = 0, for all x∈= domf =Q. Q Q Proposition 1.2.15. Let f : A→ B be a one-one function and C be a nonempty subset of A. Then, f is also one-one. C Proof. Let if possible, f (x) = f (y), for some x,y∈ C. Then, by definition of f , we have C C C f(x)=f(y). As f is one-one, we get x =y. Thus, f is one-one. C DRAFT1.2. PRELIMINARIES 11 Definition 1.2.16. Onto/Surjection A function f : A→ B is called onto (also called a −1 surjection), if f (b) =6 ∅, for each b∈ B. Equivalently, f : A→ B is onto if ‘each z∈ B has some pre-image in A’. Example 1.2.17. 1. In Definition 1.2.9, the function g is onto whereas g is not onto. 2 1 2. There are 6 onto functions from 3 to 2. For example, f(1) = 1,f(2) = 2 and f(3) = 2 is one such function. ( y if y∈A, 3. Let∅ =6 A( B. Choose a∈ A. Then, g(y) = is an onto map from a if y∈B\A. B to A. 4. There is no onto function from the set 2 to its proper superset 3. 5. There are onto functions f from the set2,3,... to its proper supersetN. One of them is f(x)=x−1. Definition 1.2.18. Bijection and equivalent set Let A and B be two sets. A function f : A→ B is said to be a bijection if f is one-one as well as onto. The sets A and B are said to be equivalent if there exists a bijection f :A→B. Example 1.2.19. 1. In Definition 1.2.9, the function g is a bijection. 2 2. The function f : 3→a,b,c defined by f(1) = c, f(2) = b and f(3) = a, is a bijection. Thus, the seta,b,c is equivalent to 3. 3. Let∅ =6 A⊆A. Then, f(x)=x is a bijection. Thus, the set A is equivalent to itself. −1 4. If f :A→B is a bijection then f : B→A is a bijection. Thus, if A is equivalent to B then B is equivalent to A. 5. The set N is equivalent to2,3,.... Indeed the function f : N→2,3,... defined by f(1) = 3, f(2) = 2 and f(n)=n+1, for n≥ 3 is a bijection. The following is known as the ‘principle of mathematical induction’ in weak form. Axiom 1.2.20. Principle of mathematical induction (PMI): Weak form Let S⊆N be a set which satisfies 1. 1∈S and 2. k+1∈S whenever k∈S. 1 Then, S =N. Fact 1.2.21. 1. Let A,B and C be sets and let f : A→ B and g : B→ C be bijections. Then, h :A→C defined by h(x) =g(f(x)) is a bijection. 1 PMI is actually a part of Peano’ axioms that defines N as: a) 1 ∈ N. b) For each n ∈ N, the successor s(n)∈N. c) 1 is not a successor of any natural number. d) If s(m) = s(n) happens for natural numbers m and n, then m =n. e) Let S ⊆N such that 1∈S and s(k)∈S, for each k ∈S. Then, S =N. DRAFT12 CHAPTER 1. BASIC SET THEORY Proof. h is one-one: Let if possible h(x) = h(y), for some x,y∈ A. Then, by definition, g(f(x)) = g(f(y)), for some f(x),f(y)∈ B. As g is one-one, we get f(x) = f(y). Now, using f is one-one, we get x =y and hence h is one-one. h is onto: Let c∈ C. Then, the condition that g is onto implies that there exists b∈ B such that g(b) = c. Also, for b∈B, the condition that f is onto implies that there exists a∈ A such that f(a) = b. Thus, we see that h(a) = g(f(a)) = g(b) = c and hence the required result follows. 2. Let A and B be two disjoint sets and let f : A→ n and g : B→ m be two bijections. ( f(x) if x∈A Then, the function h : A∪B→ m+n defined by h(x) = is a g(x)+n if x∈B bijection. 3. Fix n≥ 2 and let f : A→ n be a bijection such that for a fixed element a∈A, one has ( f(x) if f(x)≤k−1 f(a) =k. Then, g :A\a→ n−1 defined by g(x) = is f(x)−1 if f(x)≥k+1 a bijection. 4. For any positive integers n and k, there is no bijection from n to n+k. Proof. Let us fix k and prove the result by induction on n. The result is clearly true for n = 1 as k +1≥ 2. So, let the result be true for n. We need to prove it for n+1. On the contrary, assume that there exists a bijection f : n + 1→ n + 1 +k. Then, by Fact 1.2.21.3, we get a bijection g : n→ n+k, where a = n+1. Thus, we arrive at a contradiction to the induction assumption. Definition 1.2.22. Number of elements in a set A set A is said to be finite if either A is empty or A is equivalent to n, for some natural number n. A set which is not finite is called infinite. We say ‘A has n elements’ or ‘the number of elements in A is n’ to mean that ‘A is equivalent to n’. We writeA = n to mean that A has n elements. Conventionally, the number of elements in an empty set is zero. If f : n→ A is a bijection, then A can be listed asa =f(1),...,a =f(n). 1 n Fact 1.2.23. 1. LetAandB betwodisjointsets withA =mandB=n. Then,A∪B= m+n. Proof. Use Fact 1.2.21.2. 2. Any subset of n is finite. Proof. We use PMI to prove this. It is true for n = 1. Let the result be true for n−1. Now, let S⊆ n. If n6∈ S, then S⊆ n−1 and hence using PMI the result follows. If n∈ S, let T = S\n. Then, by PMI, T is finite and hence by Fact 1.2.23.1, S is finite as S is disjoint union of T andn. 3. Any subset of a finite set is finite. Proof. LetS = n, for some n∈N. Then, there is a bijection f : S→ n. Let T⊆ S. If T is empty then there is nothing to prove. Else, consider the map f : T → f(T). T DRAFT1.2. PRELIMINARIES 13 This map is a bijection. By Fact 1.2.23.2, f(T)⊆ n is finite and hence T is finite (use Fact 1.2.21.1). 4. Let A and B be two finite sets, thenA∪B=A+B−A∩B. Proof. Using (1.1), A∪B = (A\B)∪(A∩B)∪(B\A). As the sets A\B, A∩B and B\A are finite and pairwise disjoint, the result follows from Fact 1.2.23.1. 5. Let A be a nonempty finite set. Then, for any set B,A =A\B+A∩B. Proof. As A is finite, A\B and A∩B are also finite. Now, use Fact 1.2.23.1. 6. Let A be a nonempty finite set and B⊆ A, thenB≤A. In particular, if B ( A then BA. Proof. Since B =A∩B, the result follows from Fact 1.2.23.5. 7. Let n andk be two fixed positive integers. Then, there is no one-one function from n+k to n. Proof. Suppose there exists a one-one function f : n+k→ n, for some n and k. Put B =f(n+k)⊆ n. Then, notice that f : n+k→B is a bijection and hence the sets B and n+k are equivalent. Thus, by definition and Fact 1.2.23.6, n+k =B≤nn+1. Or equivalently, k 1 contradicting the assumption that k≥ 1. 8. The setN is infinite. Proof. Assume that the set N is finite andN = n, for some natural number n. Let f : N→ n be a bijection. Then, f is the restriction of f on n + 1. Thus, by n+1 Proposition 1.2.15, f is also one-one, contradicting Fact 1.2.23.7. n+1 9. Let A be a finite nonempty set and x be a fixed symbol. Now, consider the set B = (x,a)a∈A. Then,A =B. Proof. Define the function f : A→ B by f(a) = (x,a), for all a∈ A. Then, f is a bijection. 10. Let A be an infinite set and B⊇A. Then, B is infinite. Proof. If B is finite then by Fact 1.2.23.3, A is finite. A contradiction to A being an infinite set. 11. Let A be an infinite set and B be a finite set. Then, A\B is also infinite. In particular, if a∈A, then A\a is also infinite. Proof. If A\B is finite, then by Fact 1.2.23.1, the set (A\B)∪B is also finite. But A⊆ (A\B)∪B and hence by Fact 1.2.23.3, A is finite as well. A contradiction toA being an infinite set. 12. A set A is infinite if and only if there is a one-one function f :N→A. Proof. Let A be infinite. So, A6=∅. Let a ∈ A. Put f(1) = a and A = A\a. By 1 1 1 1 Fact 1.2.23.11, A is infinite. Assume that we have defined f(1),...,f(k) and obtained 1 A =A \a. As A was infinite, by Fact 1.2.23.11, A is infinite. Hence, A =6 ∅. k k−1 k k−1 k k DRAFT14 CHAPTER 1. BASIC SET THEORY Let a ∈A . Definef(k+1) =a and A =A \a . By applying induction, f k+1 k k+1 k+1 k k+1 gets defined onN. Notice that by construction a ∈/a ,...,a. Hence, f is one-one. k+1 1 k Conversely, let f :N→A be one-one. Then, f :N→f(N) is a bijection. If f(N) is finite thenN is finite as well, contradicting Fact 1.2.23.8. Hence, f(N) is infinite. As f(N)⊆A, using Fact 1.2.23.10, A is infinite as well. 13. A set is infinite if and only if it is equivalent to a proper subset of itself. Proof. Let S be an infinite set. Then, by Fact 1.2.23.12, there is a one-one function ( x, if x6∈f(N) f :N→ S. Now define a map g : S→ S\f(1) by g(x) = f(k+1), if x =f(k). Then, g is indeed a bijection. Thus, S is equivalent to its proper subset S\f(1). Conversely, let S be a set and T a proper subset of S such that there is a bijection f : S→ T. Suppose that S is finite and letS = n. Then, by Fact 1.2.23.6, T is also finite andT = m n. On the other hand, by the assumption that S is finite and there is a bijection from S to T, we have m =n, a contradiction. Exercise 1.2.24. Optional 1. Do there exist unique sets X and Y such that X\Y =1,3,5,7 and Y\X =2,4,8? 2. In a class of 60 students, all the students play either football or cricket. If 20 students play both football and cricket, determine the number of players for each game if the number of students who play football is (a) 14 more than the number of students who play cricket. (b) exactly 5 times the number of students who play only cricket. (c) a multiple of 2 and 3 and leaves a remainder 3 when divided by 5. (d) is a factor of 90 and the number of students who play cricket is a factor of 70. 1.3 More on the Principle of Mathematical Induction The following is known as the ‘principle of mathematical induction’ in strong form. Theorem 1.3.1. Principle of mathematical induction (PMI): Strong form Let S⊆N be a set which satisfies 1. 1∈S and 2. k+1∈S whenever k⊆S holds. Then, S =N. Proof. Define T =k∈ S k⊆ S. Then, 1∈ T as 1∈ S and 1⊆ S. Now, suppose k∈T. Then, by definition k⊆S. Therefore, the hypothesis implies that k+1∈S and hence k+1 = k∪k+1⊆S. Thus, k+1∈T. Hence, by using the weak form of PMI on T, we conclude that T =N, which in turn implies that S =N. DRAFT1.3. MORE ON THE PRINCIPLE OF MATHEMATICAL INDUCTION 15 Theorem 1.3.2. Another form of PMI Let S⊆Z be a set which satisfies 1. k ∈S and 0 2. k+1∈S wheneverk ,k +1,...,k⊆S. 0 0 Then,k ,k +1,...⊆S. 0 0 Proof. Consider T = x− (k − 1) x ∈ S,x ≥ k. Then, 1 ∈ T as k ∈ S and 1 = 0 0 0 k −(k −1). Now, let k⊆T. Then,k ,k +1,...,k +k−1⊆S. Hence, by the hypothesis, 0 0 0 0 0 (k +k−1)+1 =k +k∈S. Therefore, by definition of T, we have k+1∈T and hence using 0 0 the strong form of PMI, T =N. Thus, the required result follows. The next result is commonly known as the Well-Ordering Principle which states that “every nonempty subset of natural numbers contains its least element”. Theorem 1.3.3. Application of PMI in strong form: A nonempty subset ofN contains its minimum Let∅ =6 A⊆N. Then, the least element of A is a member of A. Proof. For each fixed positive integer k, let P(k) mean the statement ‘each nonempty subset A ofN that contains k, also contains its minimum’. Notice that P(1) is true. Now, assume that P(1),...,P(k) are true. We need to show that P(k +1) is true as well. Hence, consider a set A such that k +1∈ A. If1,...,k∩A =∅, then k +1 = minA, we are done. If r∈1,...,k∩A, then r≤ k and hence by induction hypothesis, P(r) is true. So, P(k +1) is true. Hence, by the strong form of PMI the required result follows. By using Theorem 1.3.2, we can also prove the following generalization of Theorem 1.3.3. The proof is similar to the proof of Theorem 1.3.3 and is left to the reader. Theorem 1.3.4. Well-ordering principle Fix k∈Z. Let A be a nonempty subset ofk,k+ 1,.... Then, A contains its minimum element. Theorem 1.3.5. Archimedean property for positive integers Let x,y∈ N. Then, there exists n∈N such that nx≥y. Proof. On the contrary assume that such an n∈N does not exist. That is, nx y for every n∈ N. That is, y−nx∈ N, for all n∈ N. Now, consider the set S =y−nx n∈ N. 0 Then, y∈S and hence S is a nonempty subset ofN . Therefore, by the well-ordering principle 0 (Theorem 1.3.4), S contains its least element, say y−mx. Then, by assumption, the integer y−(m+1)x≥ 0, y−(m+1)x∈S andy−(m+1)xy−mx. A contradicts to the minimality of y−mx. Thus, our assumption is invalid and hence the required result follows. The next result gives the equivalence of the weak form of PMI with the strong form of PMI. Theorem 1.3.6. Equivalence of PMI in weak form and PMI in strong form Fix a natural number k and let P(n) be a statement about a natural number n. Suppose that P means the 0 statement ‘P(n) is true, for each n∈N,n≥ k ’. Then, ‘P can be proved using the weak form 0 of PMI’ if and only if ‘P can be proved using the strong form of PMI’. DRAFT16 CHAPTER 1. BASIC SET THEORY Proof. Let us assumethat thestatement P has been proved usingthe weak form of PMI. Hence, P(k ) is true. Further, whenever P(n) is true, we are able to establish that P(n+1) is true. 0 Therefore, we can establish that P(n+1) is true if P(k ),...,P(n) are true. Hence, P can be 0 proved using the strong form of PMI. So, now let us assume that the statement P has been proved using the strong form of PMI. Now, define Q(n) to mean ‘P(ℓ) holds for ℓ = k ,k + 1,...,n’. Notice that Q(k ) is true. 0 0 0 Supposethat Q(n) is true (this means that P(ℓ) is true forℓ =k ,k +1,...,n). By hypothesis, 0 0 weknowthatP hasbeenprovedusingthestrongformofPMI.Thatis,P(n+1)istruewhenever P(ℓ) is true for ℓ =k ,k +1,...,n. This, in turn, means that Q(n+1) is true. Hence, by the 0 0 weak form of PMI, Q(n) is true for all n≥ k . Thus, we are able to prove P using the weak 0 form of PMI. Theorem 1.3.7. Optional: Application of PMI in weak form: AM-GM inequality Fix a positive integer n and let a ,a ,...,a be non-negative real numbers. Then 1 2 n a +···+a √ 1 n n Arithmetic Mean (AM):= ≥ a ···a =: (GM) Geometric Mean. 1 n n Proof. The inequality clearly holds for n = 1 and 2. Assume that it holds for every choice of n non-negative real numbers. Now, leta ,...,a ,a bea set ofn+1non-negative real numbers 1 n n+1 a +a +···+a 1 2 n+1 with a = maxa ,...,a and a = mina ,...,a . Define A = . Then, 1 1 n+1 n+1 1 n+1 n+1 note that a ≥ A≥ a . Hence, (a −A)(A−a )≥ 0, i.e., A(a +a −A)≥ a a . 1 n+1 1 n+1 1 n+1 1 n+1 Now, apply induction hypothesis on the n non-negative real numbers a ,...,a ,a +a −A 2 n 1 n+1 to get p a +···+a +(a +a −A) 2 n 1 n+1 n a ·····a ·(a +a −A)≤ =A. 2 n 1 n+1 n n+1 So, wehaveA ≥ (a ·a ·····a ·(a +a −A))·A≥ (a ·a ·····a )a a . Therefore, 2 3 n 1 n+1 2 3 n 1 n+1 by PMI, the inequality holds, for each n∈N. Inthenextexample, weillustratetheuseofPMItoestablishsomegiven identities (properties, statements) involving natural numbers. n(n+1) Example 1.3.8. Prove that 1+2+···+n = . 2 n(n+1) Ans: The result is clearly true for n = 1. So, let us assume that 1+2+···+n = . 2 Then, using the induction hypothesis, we have n(n+1) n+1 1+2+···+n+(n+1) = +(n+1) = (n+2). 2 2 Thus, the result holds for n+1 and hence by the weak form of PMI, the result follows. Exercise 1.3.9. Optional Prove using PMI. n(n+1)(2n+1) 2 2 2 1. 1 +2 +···+n = . 6 2 2. 1+3+···+(2n−1) =n , for all n∈N. 3. n(n+1) is even, for all n∈N. 3 4. 3 divides n −n, for all n∈N. DRAFT1.3. MORE ON THE PRINCIPLE OF MATHEMATICAL INDUCTION 17 5 5. 5 divides n −n, for all n∈N. Practice1.3.10. WronguseofPMI:Canyoufindtheerror? The following isan incorrect proof of ‘if a set of n balls contains a green ball then all the balls in the set are green’. Find the error. Proof. The statement holds trivially for n = 1. Assume that the statement is true for n≤ k. Take a collection B of k +1 balls that contains at least one green ball. From B , pick a k+1 k+1 collection B of k balls that contains at least one green ball. Then, by the induction hypothesis, k each ball in B is green. Now, remove one ball from B and put the ball which was left out in k k ′ ′ the beginning. Call it B . Again by induction hypothesis, each ball in B is green. Thus, each k k ball in B is green. Hence, by PMI, our proof is complete. k+1 Exercise 1.3.11. Optional n+1 n P x −1 2 n k 1. Let x∈R with x =6 1. Then, prove that 1+x+x +···+x = x = . x−1 k=0 2. Let a,a+d,a+2d,...,a+(n−1)d be the first n terms of an arithmetic progression. Then, n−1 X n S = (a+id) =a+(a+d)+···+(a+(n−1)d) = (2a+(n−1)d). 2 i=0 2 n−1 3. Let a,ar,ar ,...,ar be the first n terms of a geometric progression, with r =6 1. Then, n n−1 P r −1 n−1 i S =a+ar+···+ar = ar =a . r−1 i=0 4. Prove that 3 (a) 6 divides n −n, for all n∈N. 7 (b) 7 divides n −n, for all n∈N. 2n (c) 3 divides 2 −1, for all n∈N. 2n (d) 9 divides 2 −3n−1, for all n∈N. 9 (e) 10 divides n −n, for all n∈N. 2n+2 4 2 (f) 12 divides 2 −3n +3n −4, for all n∈N.   2 n(n+1) 3 3 3 (g) 1 +2 +···+n = . 2 5. Determine a formula for 1·2+2·3+3·4+···+(n−1)·n and prove it. 6. Determine a formula for 1·2·3+2·3·4+3·4·5+···+(n−1)·n·(n+1) and prove it. 7. Determine a formula for 1·3·5+2·4·6+···+n·(n+2)·(n+4) and prove it. 8. Informative For all n≥ 32, there exist nonnegative integers x and y such that n = 5x+9y. Hint: First prove it for the starting 5 numbers, 32,33,34,35,36. 9. Informative Prove that, for all n≥ 40, there exist nonnegative integers x and y such that n = 5x+11y. n 2 10. For every positive integer n≥ 3 prove that 2 n 2n+1. DRAFT18 CHAPTER 1. BASIC SET THEORY 11. Let r∈R with r −1. Then, prove that n (1+r) ≥ 1+rn for all n∈N. (1.3) 12. Informative Prove that for µ 0,   p 2 2 Y p(p+1) 1 p (p+1) p(p+1)(2p+1) 2 (1+lµ )≥ 1+ µ + − µ . 2 2 4 6 l=1 13. Informative By an L-shaped piece, we mean a piece of the type shown in the picture. n n Consider a 2 ×2 square with one unit square cut. See picture. A B α β C γ L-shaped piece 4×4 and 8×8 squares with a unit square cut n n Show that a 2 ×2 square with one unit square cut, can be covered with L-shaped pieces. 5 5 4 3 2 14. InformativeVerifythat (k+1)−k = 5k +10k +10k +5k+1. Now, putk = 1,2,...,n n n n n n P P P P P 5 4 3 2 and add to get (n+1) −1 = 5 k +10 k +10 k +5 k+ 1. Now, use k=1 k=1 k=1 k=1 k=1 n n n n n P P P P P 3 2 4 the formula’s for k , k , k and 1 to get a expression for k . k=1 k=1 k=1 k=1 k=1 15. Informative: A general result than AM-GM (a) Let a ,...,a be nonnegative real numbers such that the sum a +··· + a = 5. 1 9 1 9 a +a a +a 1 2 1 2 Assume that a =6 a . Consider , ,a ,...,a . Argue that a ···a ≤ 1 2 3 9 1 9 2 2   2 a +a 1 2 a ···a . 3 9 2 (b) Let a ,...,a be any nonnegative real numbers such that the sum a +···+a =r . 1 n 1 n 0 Argue that the highest value of a ···a is obtained when a =··· =a =r /n. 1 n 1 n 0 (c) Let a ,...,a be fixed nonnegative real numbers such that the sum a +···+a =r . 1 n 1 n 0 n Conclude from the previous item that (r /n) ≥a ···a , the AM-GM inequality. 0 1 n 1.4 Integers In this section, we study some properties of integers. We start with the ‘division algorithm’. Lemma 1.4.1. Division algorithm Let a and b be two integers with b 0. Then, there exist unique integers q,r such that a =qb+r, where 0≤r b. The integer q is called the quotient and r, the remainder. Proof. Existence: Take S =a+bxx∈Z∩N . Then, a+ab∈S. Hence, S is a nonempty 0 subset of N . Therefore, by the Well-Ordering Principle, S contains its minimum, say s . So, 0 0 s =a+bx , for some x ∈Z. Notice that s ≥ 0. We claim that s b. 0 0 0 0 0 DRAFT1.4. INTEGERS 19 If s ≥b then s −b≥ 0 and hence s −b =a+b(x −1)∈S, a contradiction to s being the 0 0 0 0 0 minimum element of S. Now, put q =−x and r = s . Thus, we have obtained q and r such 0 0 that a =qb+r, with 0≤r b. Uniqueness: Assumethatthereexistintegersq ,q ,r andr satisfyinga =q b+r ,0≤r b 1 2 1 2 1 1 1 anda =q b+r ,0≤r b. Withoutlossofgenerality,weassumer ≤r . Then,0≤r−r b. 2 2 2 1 2 2 1 Notice that r −r = (q −q )b. So, 0≤ (q −q )bb. But the only integer multiple of b which 2 1 1 2 1 2 lies in 0,b) is 0. Hence, q −q = 0. Thus, r =r as well. This completes the proof. 1 2 1 2 Definition 1.4.2. Divisibility 1. Divisor Let a,b∈Z with b6= 0. If a =bc, for some c∈Z then b is said to divide (be a divisor of) a and is denoted ba. Discussion: Ifaisanonzerointegerthenthesetofpositivedivisorsofaisalwaysnonempty (as 1a) and finite (as a positive divisor of a is less than or equal toa). 2. Greatest common divisor Let a and b be two nonzero integers. Then, the set S of their common positive divisors is nonempty and finite. Thus, S contains its greatest element. This element is called thegreatest common divisor of a and b and is denoted gcd(a,b). On similar lines one can define the greatest common divisor of non-zero integers a ,a ,...,a as the largest positive integer that divides each of a ,a ,...,a , denoted 1 2 n 1 2 n gcd(a ,...,a ). 1 n 3. Relatively prime/Co-primeintegers An integer a is said to berelatively prime to an integer b if gcd(a,b) = 1. Or, two integersa andb are said to beco-prime if gcd(a,b) = 1. The next remark follows directly from the definition and the division algorithm. Remark 1.4.3. Let a,b∈Z\0 and d = gcd(a,b). Then, for any positive common divisor c of a and b, one has cd. The next result is often stated as ‘the gcd(a,b) is an integer linear combination of a and b’. Theorem 1.4.4. Be´zout’s identity Let a and b be two nonzero integers. Then, there exist integers x ,y such that d =ax +by , where d = gcd(a,b). 0 0 0 0 Proof. Consider the set S =ax+by x,y∈Z∩N. Then, either a∈ S or−a∈ S. Thus, S is a nonempty subset ofN. Hence, by the Well-ordering principle, S contains its least element, say d. As d∈S, we have d=ax +by , for some x ,y ∈Z. We claim that d= gcd(a,b). 0 0 0 0 Notethatdispositive. Letcbeanypositivecommondivisorofaandb. Then,cax +by =d 0 0 as x ,y ∈Z. We now show that da and db. 0 0 By division algorithm, there exist integers q andr such that a =dq+r, with 0≤r d. Thus, we need to show that r = 0. On the contrary, assume that 0r d. Then r =a−dq =a−q(ax +by ) =a(1−qx )+b(−qy )∈ax+byx,y∈Z. 0 0 0 0 DRAFT20 CHAPTER 1. BASIC SET THEORY Hence, r is a positive integer in S which is strictly less than d. This contradicts the fact that d is the least element of S. Thus, r = 0 and hence da. Similarly, db. Thedivisionalgorithmgivesusanideatoalgorithmicallycomputethegreatestcommondivisor of two integers, commonly known as the Euclid’s algorithm. Discussion 1.4.5. 1. Note that d, the number obtained by the application of the Well- ordering principle in the proof of Theorem 1.4.4 has the property that d divides ax+by, for all x,y∈Z. So, for every choice of integers x,y, gcd(a,b) divides ax+by. 2. Let a,b∈ Z\0. By division algorithm, a =bq +r, for some integers q,r∈ Z with 0≤r b. Then, gcd(a,b) =gcd(a,b) = gcd(b,r). To show the second equality, note that r = a−bq and hence gcd(a,b) r. Thus, gcd(a,b)gcd(b,r). Similarly, gcd(b,r) gcd(a,b) as a =bq+r. 3. We can now apply the above idea repeatedly to find the greatest common divisor of two given nonzero integers. This is called the Euclid’s algorithm. For example, to find gcd(155,−275), we proceed as follows −275 = (−2)·155+35 (so, gcd(−275,155) = gcd(155,35)) 155 = 4·35+15 (so, gcd(155,35) = gcd(35,15)) 35 = 2·15+5 (so, gcd(35,15) = gcd(15,5)) 15 = 3·5 (so, gcd(15,5) = 5). To write 5= gcd(155,−275) in the form 155x +(−275)y , notice that 0 0 5 = 35−2·15 = 35−2(155−4·35) = 9·35−2·155 = 9(−275+2·155)−2·155 = 9·(−275)+16·155. Also, notethat275 = 5·55and155 = 5·31andthus,5 = (9+31x)·(−275)+(16+55x)·155, for all x∈ Z. Therefore, we see that there are infinite number of choices for the pair 2 (x,y)∈Z , for which d =ax+by. 4. Euclid’salgorithm Ingeneral,giventwononzerointegersaandb,thealgorithmproceeds as follows: a = bq +r with 0≤r b, b =r q +r with 0≤r r , 0 0 0 0 1 1 1 0 r = r q +r with 0≤r r , r =r q +r with 0≤r r , 0 1 2 2 2 1 1 2 3 3 3 2 . . . . . = . r = r q +r with 0≤r r , r =r q . ℓ−1 ℓ ℓ+1 ℓ+1 ℓ+1 ℓ ℓ ℓ+1 ℓ+2 The process will take at most b−1 steps as 0≤ r b. Also, note that gcd(a,b) = r 0 ℓ+1 and r can be recursively obtained, using backtracking. That is, ℓ+1 r =r −r q =r −q (r −r q )=r (1+q q )−q r =··· . ℓ+1 ℓ−1 ℓ ℓ+1 ℓ−1 ℓ+1 ℓ−2 ℓ−1 ℓ ℓ−1 ℓ+1 ℓ ℓ+1 ℓ−2 DRAFT