BCA124 CU- BCA-Sem 2 -Discrete Mathematical Structures(Draft 3)-converted

50 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 3- RELATION 51 Structure 3.0. Learning Objectives 3.1. Introduction 3.2. Definition 3.3. Domain and range of a relation 3.4. Types of relation 3.4.1 Congruence Modulo: 3.4.2 Congruence Class: 3.5. Composition of relations 3.6. Representation of Relation 3.7. Pictorial properties Of Relation 3.7.1 Reflexive Relation 3.7.2 Symmetric Relation 3.7.3 Antisymmetric Relation 3.7.4 Asymmetric Relation 3.7.5 Transitive Relation 3.8. Partial order in relation 3.9. Summary 3.10. Keywords 3.11. Learning Activity 3.12. Unit End Questions 3.13. References 3.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • Explain the concept of Relation • Comprehend Types of relation and Composition of relations, • State Domain and range of a relation, • Enumerate Pictorial representation and Properties of relation • Explain the Partial order in relation CU IDOL SELF LEARNING MATERIAL (SLM)

3.1 INTRODUCTION The concept of relation in math refers to an association of two objects or two variables based some property possessed by them.A relation between two sets is a collection of ordered pairs containing one object from each set. If the object x is from the first set and the object y is from the second set, then the objects are said to be related if the ordered pair (x, y) is in the relation. A function is a type of relation. But a relation is allowed to have the object x in the first set to be related to more than one object in the second set. So, a relation may not be represented by a function machine, because, given the object x to the input of the machine, the machine couldn't spit out a unique output object that is paired to x. Relation, in logic, a set of ordered pairs, triples, quadruples, and so on. A set of ordered pairs is called a two-place (or dyadic) relation; a set of ordered triples is a three-place (or triadic) relation; and so on. In general, a relation is any set of ordered n-tuples of objects. Important properties of relations include symmetry, transitivity, and reflexivity. We will also study different types of relations: 3.2 DEFINITION: A relation from a set A to a set B is any subset of A×B (Cartesian Product of Set A & B), is represented by ‘R’ which indicates relation such that xRy makes sense for xϵA and yϵ B. We can represent R by the set of ordered pairs (x, y) for which the relation holds, that is {(x, y) | xRy}. Example: If A= {1, 2, 3, 4} then the relation normally written x < y would be: {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} 52 CU IDOL SELF LEARNING MATERIAL (SLM)

For Example: 1. Rachel is the daughter of Noah. This statement shows the relation between two persons. The relation (R) being ‘is daughter of’. 2. 5 is less than 9. This statement shows the relation between two numbers. The relation (R) being ‘is less than’. If A and B are two non-empty sets, then the relation R from A to B is a subset of A x B, i.e., R ⊆ A x B. If (a, b) ∈ R, then we write a R b and is read as 'a' related to 'b' 3.3 DOMAIN AND RANGE OF RELATION Domain of R: The domain of R is the set of first coordinates in R & denoted by dom R From above example dom R = {1,1,1,2,2,3} or {x |x ∈A and (x, y) ∈ R for some y ϵ B} Range of R: The range of R is the set of second coordinates in R & denoted by ran R From above example Ran R = {2, 3, 4, 3, 4, 4} or {y | y ϵ B and (x, y) ϵ R for some x ϵ A} Example 1: In the given ordered pair (4, 6); (8, 4); (4, 4); (9, 11); (6, 3); (3, 0); (2, 3) find the 53 following relations. Also, find the domain and range. (a) Is two less than (b) Is less than (c) Is greater than (d) Is equal to Solution: (a) R₁ is the set of all ordered pairs whose 1ˢᵗ component is two less than the 2ⁿᵈ component. CU IDOL SELF LEARNING MATERIAL (SLM)

Therefore, R₁ = {(4, 6); (9, 11)} Also, Domain (R₁) = Set of all first components of R₁ = {4, 9} and Range (R₂) = Set of all second components of R₂ = {6, 11} (b) R₂ is the set of all ordered pairs whose 1ˢᵗ component is less than the second component. Therefore, R₂ = {(4, 6); (9, 11); (2, 3)}. Also, Domain (R₂) = {4, 9, 2} and Range (R₂) = {6, 11, 3} (c) R₃ is the set of all ordered pairs whose 1ˢᵗ component is greater than the second component. Therefore, R₃ = {(8, 4); (6, 3); (3, 0)} Also, Domain (R₃) = {8, 6, 3} and Range (R₃) = {4, 3, 0} (d) R₄ is the set of all ordered pairs whose 1ˢᵗ component is equal to the second component. Therefore, R₄ = {(3, 3)} Also, Domain (R) = {3} and Range (R) = {3} Example 2: Let A = {1, 2, 3, 4, 5} and B = {p, q, r, s}. Let R be a relation from A in B defined by R = {1, p}, (1, r), (3, p), (4, q), (5, s), (3, p)} Find domain and range of R. Solution: Given R = {(1, p), (1, r), (4, q), (5, s)} Domain of R = set of first components of all elements of R = {1, 3, 4, 5} Range of R = set of second components of all elements of R = {p, r, q, s} Example 3: Determine the domain and range of the relation R defined by 54 R = {x + 2, x + 3}: x ∈ {0, 1, 2, 3, 4, 5} Solution: Since, x = {0, 1, 2, 3, 4, 5} Therefore, x = 0 ⇒ x + 2 = 0 + 2 = 2 and x + 3 = 0 + 3 = 3 x = 1 ⇒ x + 2 = 1 + 2 = 3 and x + 3 = 1 + 3 = 4 CU IDOL SELF LEARNING MATERIAL (SLM)

x = 2 ⇒ x + 2 = 2 + 2 = 4 and x + 3 = 2 + 3 = 5 x = 3 ⇒ x + 2 = 3 + 2 = 5 and x + 3 = 3 + 3 = 6 x = 4 ⇒ x + 2 = 4 + 2 = 6 and x + 3 = 4 + 3 = 7 x = 5 ⇒ x + 2 = 5 + 2 = 7 and x + 3 = 5 + 3 = 8 Hence, R = {(2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8)} Therefore, Domain of R = {a : (a, b) ∈R} = Set of first components of all ordered pair belonging to R. Therefore, Domain of R = {2, 3, 4, 5, 6, 7} Range of R = {b: (a, b) ∈ R} = Set of second components of all ordered pairs belonging to R. Therefore, Range of R = {3, 4, 5, 6, 7, 8} 3.4 TYPES OF RELATIONS Empty Relation: A relation R in a set X, is called an empty relation, if no element of X is related to any element of X, i.e., R = Φ ⊂ X × X Universal Relation: A relation R in a set X, is called universal relation, if each element of X is related to every element of X, i.e., R = X × X Reflexive Relation: A relation R defined on a set A is said to be reflexive, if (x, x) ∈ R, ∀ x ∈ A or xRx, ∀ x ∈ R Symmetric Relation: A relation R defined on a set A is said to be symmetric, if (x, y) ∈ R ⇒ (y, x) ∈ R, ∀ x, y ∈ A or xRy ⇒ yRx, ∀ x, y ∈ R. Transitive Relation: A relation R defined on a set A is said to be transitive, if 55 (x, y) ∈ R and (y, z) ∈ R ⇒ (x, z) ∈ R, ∀ x, y, z ∈ A or xRy, yRz ⇒ xRz, ∀ x, y, z∈ R. CU IDOL SELF LEARNING MATERIAL (SLM)

Equivalence Relation: A relation R defined on a set A is said to be an equivalence relation if R is reflexive, symmetric and transitive. The three most important properties for a relation R on a set A are the reflexive, symmetric and transitive properties. R is reflexiveif xRx forall x. R is symmetricif xRy→yRx forall x, y. R is transitiveif xRy and yRz→xRz forall x, y, z. Example 1: 1. Let A = {1, 2, 3, 4} & let R= {(1, 3), (4, 2), (2, 4), (2, 3), (3, 1)} Not Reflexive: Since (1, 1) ∉ R Not Symmetric: (2, 3) ϵ R but (3, 2) ∉ R Not Transitive: (2, 3) ϵ R and (3,1) ϵ R but (2, 1) ∉ R 2. x Ry ↔|x - y| < 3 Reflexive: Since for all x, |x – x| = 0 which is less than 3. Symmetric: Since |y – x| = |x – y|. Not Transitive: For example, 1R3 and 3R5 but it is not true that 1R5. Example 2: If A = {1, 2, 3, 4} then R = {(1, 1) (2, 2), (1, 3), (2, 4), (3, 3), (3, 4), (4, 4)}. Is a relation reflexive? Solution: The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2), (3, 3), (4, 4) ∈ R. Example 3: Let A = {1, 2, 3} and R = {(1, 2), (2, 2), (3, 1), (1, 3)}. Is the relation R reflexive or irreflexive? Solution: The relation R is not reflexive as for every a ∈ A, (a, a) ∉ R, i.e., (1, 1) and (3, 3) ∉ R. The relation R is not irreflexive as (a, a) ∉ R, for some a ∈ A, i.e., (2, 2) ∈ R. Example 4: Let A = {1, 2, 3} and R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}. Is a relation R symmetric or not? Solution: The relation is symmetric as for every (a, b) ∈ R, we have (b, a) ∈ R, i.e., (1, 2), (2, 1), (2, 3), (3, 2) ∈ R but not reflexive because (3, 3) ∉ R. 56 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 5: Let A = {1, 2, 3} and R = {(1, 1), (2, 2)}. Is the relation R antisymmetric? Solution: The relation R is antisymmetric as a = b when (a, b) and (b, a) both belong to R. Example 6: Let A = {4, 5, 6} and R = {(4, 4), (4, 5), (5, 4), (5, 6), (4, 6)}. Is the relation R antisymmetric? Solution: The relation R is not antisymmetric as 4 ≠ 5 but (4, 5) and (5, 4) both belong to R. Example 7: Let A = {1, 2, 3} and R = {(1, 2), (2, 1), (1, 1), (2, 2)}. Is the relation transitive? Solution: The relation R is transitive as for every (a, b) (b, c) belong to R, we have (a, c) ∈ R i.e., (1, 2) (2, 1) ∈ R ⇒ (1, 1) ∈ R. Equivalence Classes: Given an arbitrary equivalence relation R in an arbitrary set X, R divides X into mutually disjoint subsets A, called partitions or sub-divisions of X satisfying • all elements of Ai are related to each other, for all i. • no element of Ai is related to any element of Aj, i ≠ j • Ai ������ Aj = X and Ai ∩ Aj = 0, i ≠ j. The subsets Ai and Aj are called equivalence classes. Anti-symmetric Relation: If following below condition is satisfied (a, b) ϵR and (b, a) ϵ R implies a= b Refer the 1st example above a relation R on set A is not anti-symmetric as (1, 3) ϵR and (3, 1) ϵ R and 1≠ 3 3.4.1 Congruence Modulo: Suppose A be the set of integers &n be fixed positive integer. So, relation Rn on A by aRnb if a – b is an integral multiple of n. So, a – b =mn where m is some integer. Thus,a is congruent to b modulo n& is represented as a ≡ b mod n Let’s check the equivalence relation Reflexive: a – a = 0.n so that a ≡ a mod n for each integer n Symmetric: a ≡ b mod n then a – b = mn where m is some integer & b – a = (–m) n so that we have b ≡ a mod n 57 CU IDOL SELF LEARNING MATERIAL (SLM)

Transitive: If a ≡ b mod n & b ≡ c mod n then a – b = mn & b – c = kn where m&k are integers. So, after adding these two equations we have a – c = (m + k) n & we can conclude that a ≡ c mod n. 3.4.2 Congruence Class: If x is a given integer then [x] denote the set of all integers y such that x ≡ y mod n then [x] is known as Equivalence /Congruence Class containing x integer &xis called as representative of the congruence class. [x] = {x + mn | m is any integer} 3.5 COMPOSITION OF RELATION: • Let R be the relation from A to B & S a relation from B to C. • The composition of R and S is denoted by R ∘ S / RS is the relation from A to C which is given by a RS c if there is an element b ϵ B such that a R b and b S c • Set B serves as an intermediary for establishing a correspondence between A & C. Example: 1. If A = {1, 2, 3}, B= {5,6} and C = {a, b, c} Let R = {(1,5), (1,6), (2,6)} be a relation from A to B & Let S = {(5, a), (6, c)} be a relation from B to C. Then R∘S= {(1, a), (1, c), (2, c)} is a relation from A to C 2. If R (x)= x + 1 and S (y) = y2 are the functions defined on the set of real numbers then (R∘S) (x) = S (R (x)) = (x + 1)2 and (S∘R) (x) = R (S(x)) = x2+ 1 Example 1:Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider the relation R1 from X to Y and R2 from Y to Z. R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)} R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)} 58 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 3.1(a): Relation R1 Fig 3.1(b): Relation R2 Find the composition of relation (i) R1 ∘ R2 (ii) R1∘ R1-1 Solution: (i) The composition relation R1 o R2 as shown in fig: Fig 3.2: R1 ∘ R2 R1 ∘ R2 = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)} (ii) The composition relation R1 ∘ R1-1 as shown in fig: Fig 3.3: R1∘R1-1 59 R1∘R1-1 = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)} CU IDOL SELF LEARNING MATERIAL (SLM)

3.6 REPRESENTATION OF RELATION The relation in math from set A to set B is expressed in different forms. (i) Roster form (ii) Set builder form (iii) Arrow diagram i. Roster form: ● In this, the relation (R) from set A to B is represented as a set of ordered pairs. ● In each ordered pair 1st component is from A; 2nd component is from B. ● Keep in mind the relation we are dealing with. (>, < etc.) For Example: 1. If A = {p, q, r} B = {3, 4, 5} then R = {(p, 3), (q, 4), (r, 5)} Hence, R ⊆ A × B 2. Given A = {3, 4, 7, 10} B = {5, 2, 8, 1} then the relation R from A to B is defined as ‘is less than’ and can be represented in the roster form as R = {(3, 5) (3, 8) (4, 5), (4, 8), (7, 8)} Here, 1ˢᵗ component < 2ⁿᵈ component. In roster form, the relation is represented by the set of all ordered pairs belonging to R. If A = {-1, 1, 2} and B = {1, 4, 9, 10} If a R b means a² = b Then, R (in roster form) = {(-1, 1), (1, 1), (2, 4) ii. Set builder form: In this form, the relation R from set A to set B is represented as R = {(a, b): a ∈ A, b ∈ B, a... b}, the blank space is replaced by the rule which associates a and b. For Example: Let A = {2, 4, 5, 6, 8} and B = {4, 6, 8, 9} Let R = {(2, 4), (4, 6), (6, 8), (8, 10) then R in the set builder form, it can be written as R = {a, b}: a ∈ A, b ∈ B, a is 2 less than b} iii. Arrow diagram: - Pictorial Representation ● Draw two circles representing Set A and Set B. ● Write their elements in the corresponding sets, i.e., elements of Set A in circle A and elements of Set B in circle B. ● Draw arrows from A to B which satisfy the relation and indicate the ordered pairs. 60 CU IDOL SELF LEARNING MATERIAL (SLM)

For Example: 1. If A = {3, 4, 5} B = {2, 4, 6, 9, 15, 16, 25}, then relation R from A to B is defined as ‘is a positive square root of’ and can be represented by the arrow diagram as shown. Here R = {(3, 9); (4, 16); (5, 25)} Fig 3.4: Relation from A to B In this form, the relation R from set A to set B is represented by drawing arrows from 1ˢᵗ component to 2ⁿᵈ components of all ordered pairs which belong to R. 2. If A = {2, 3, 4, 5} and B = {1, 3, 5} and R be the relation 'is less than' from A to B, then R = {(2, 3), (2, 5), (3, 5), (4, 5)} Fig 3.5: Relation from A to B 61 3.7 PICTORIALPROPERTIES OF RELATION: A binary relation R defined on a set A may have the following properties: • Reflexivity • Irreflexivity • Symmetry • Antisymmetry CU IDOL SELF LEARNING MATERIAL (SLM)

• Asymmetry • Transitivity 3.7.1 Reflexive Relation A binary relation R is called reflexive if and only if ∀a∈A, aRa. So, a relation R is reflexive if it relates every element of A to itself. Examples of reflexive relations: 1. The relation ≥ (“is greater than or equal to”) on the set of real numbers. 2. Similarity of triangles. 3. The relation R= {(1,1), (1,2), (2,2), (3,3), (3,1)} on the set A= {1,2,3}. Fig 3.6: Reflexive Relation Reflexive relations are always represented by a matrix that has 1 on the main diagonal. The digraph of a reflexive relation has a loop from each node to itself. Irreflexive Relation: A binary relation R on a set A is called irreflexive if aRa does not hold for any a RA. This means that there is no element in R which is related to itself. Examples of irreflexive relations: 1. The relation < (“is less than”) on the set of real numbers. 2. Relation of one person being son of another person. 3. The relation R= {(1,2), (2,1), (1,3), (2,3), (3,1)} on the set A= {1,2,3}. 62 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 3.7: Irreflexive Relation The matrix of an irreflexive relation has all 0′s on its main diagonal. The directed graph for the relation has no loops. 3.7.2 Symmetric Relation A binary relation R on a set A is called symmetric if for all a,b∈A it holds that if aRb then bRa. In other words, the relative order of the components in an ordered pair does not matter – if a binary relation contains an (a, b) element, it will also include the symmetric element (b, a). Examples of symmetric relations: 1. The relation = (“is equal to”) on the set of real numbers. 2. The relation “is perpendicular to” on the set of straight lines in a plane. 3. The relation R= {(1,1), (1,2), (2,1), (1,3), (3,1)} on the set A= {1,2,3}. Fig 3.8: Symmetric Relation For a symmetric relation, the logical matrix M is symmetric about the main diagonal. The transpose of the matrix MT is always equal to the original matrix M. In a digraph of a symmetric relation, for every edge between distinct nodes, there is an edge in the opposite direction. 3.7.3 Antisymmetric Relation A binary relation R on a set A is said to be antisymmetric if there is no pair of distinct elements of A each of which is related by R to the other. So, an antisymmetric relation R can include both ordered pairs (a, b) and (b, a) if and only if a=b. Examples of antisymmetric relations: 1. The relation ≥ (“is greater than or equal to”) on the set of real numbers. 2. The subset relation ⊆ on a power set. 63 CU IDOL SELF LEARNING MATERIAL (SLM)

3. The relation R= {(1,1), (2,1), (2,3), (3,1), (3,3)} on the set A= {1,2,3}. Fig 3.9: Anti-Symmetric Relation In a matrix M=[aij] representing an antisymmetric relation R, all elements symmetric about the main diagonal are not equal to each other: aij≠aji for i≠j. The digraph of an antisymmetric relation may have loops, however connections between two distinct vertices can only go one way. 3.7.4 Asymmetric Relation An asymmetric binary relation is similar to antisymmetric relation. The difference is that an asymmetric relation R never has both elements aRb and bRa even if a=b. Every asymmetric relation is also antisymmetric. The converse is not true. If an antisymmetric relation contains an element of kind (a, a), it cannot be asymmetric. Thus, a binary relation R is asymmetric if and only if it is both antisymmetric and irreflexive. Examples of asymmetric relations: 1. The relation > (“is greater than”) on the set of real numbers. 2. The family relation “is father of”. 3. The relation R= {(2,1), (2,3), (3,1)} on the set A= {1,2,3}. Fig 3.10: Asymmetric Relation 64 CU IDOL SELF LEARNING MATERIAL (SLM)

The matrix for an asymmetric relation is not symmetric with respect to the main diagonal and contains no diagonal elements. The digraph of an asymmetric relation must have no loops and no edges between distinct vertices in both directions. 3.7.5 Transitive Relation A binary relation R on a set A is called transitive if for all a,b,c∈A it holds that if aRb and bRc, then aRc. This condition must hold for all triples a, b, c in the set. If there exists some triple a,b,c∈A such that (a,b)∈R and (b,c)∈R, but (a,c)∉R, then the relation R is not transitive. Examples of transitive relations: 1. The relation > (“is greater than”) on the set of real numbers. 2. The relation “is parallel to” on the set of straight lines. 3. The relation R= {(1,2), (1,3), (2,2), (2,3), (3,3)} on the set A= {1,2,3}. Fig 3.11: Transitive Relation In a matrix M=[aij] of a transitive relation R, for each pair of (i, j) − and (j, k) −entries with value 1 there exists the (i, k) −entry with value 1. The presence of 1′s on the main diagonal does not violate transitivity. Example: The binary relation S = {(b, d), (c, a), (c, b), (c, d), (d, a)} is defined on the set A = {a, b, c, d}. Determine the property of S Solution: The relation S is not reflexive since, for example, (a, a) ∉S. The relation S is irreflexive since it does not contain the diagonalelements (a,a), (b,b), (c,c), and (d,d). S is not symmetric. For example, (b,d)∈S, but (d,b)∉S. The relation S is asymmetric since the reverse of every ordered pair is not an element of S. 65 CU IDOL SELF LEARNING MATERIAL (SLM)

S is not transitive. For example, (b,d),(d,a)∈S, but (b,a)∉S. 3.8 PARTIAL ORDER RELATIONS Definitions: A binary relation R on a non-empty set A is called a (non-strict) partial order relation or partial ordering if and only if the relation is • reflexive • antisymmetric, and • transitive. To denote a partial order relation, we use the notation ≼, so instead of aRb we often write a≼b. If a≼b and a≠b, then we usually write a≺b. In this case, the relation is called a strict partial order on set A. It is irreflexive, antisymmetric, and transitive. A set A together with a partial order relation ≼ is called a partially ordered set or poset and is denoted by (A, ≼). Two elements a and b of a partially ordered set (A, ≼) are said to be comparable, if and only if, either a≼b or b≼a. Otherwise we say that a and b are noncomparable or incomparable. In a partially ordered set, it is not necessary that every pair of elements a and b be comparable. When all the elements of a set A are comparable, the relation is called a total ordering. Examples of Partial Order Relations Subset Relation The subset relation is denoted by ⊆ and is defined on the power set P(A), where A is any set of elements. For any subset Ai of P(A), the following is true: Ai⊆Ai. Hence, the relation ⊆ is reflexive. Suppose A1, A2 are two any subsets of P(A). If A1⊆A2 and A2⊆A1, then by definition of set equality, A1=A2. This means that the subset relation is antisymmetric. Let A1⊆A2 and A2⊆A3. Consider an arbitrary element a∈A1. Since A1⊆A2, we have a∈A2. Similarly, since A2⊆A3, we have a∈A3. Hence, the relation ⊆ is transitive. We see that the subset relation on the power set P(A) is reflexive, antisymmetric, and transitive. So, it is a partial ordering. Divisibility Relation The divisibility relation, denoted by “|”, on the set of natural numbers N= {1,2, 3…} is another classic example of a partial order relation. The relation “|” is reflexive, because any a∈N divides itself. 66 CU IDOL SELF LEARNING MATERIAL (SLM)

The relation “|” is antisymmetric. Indeed, if a∣b, then ak=b, where k is an integer. Similarly, if b∣a, then bℓ=a, where ℓ is an integer. Hence, akℓ=a,⇒kℓ=1. The last equation holds if only k=ℓ=1, which means that a=b. The relation “|” is transitive. Suppose a∣b and b∣c. Then ak=b and bℓ=c, where k,ℓ are certain integers. Hence akℓ=c, and kℓ is an integer. This means that a∣c. Some Other Examples The following relations are partial orders: • “The “less than or equal to” relation, denoted by ≤, on the set of real numbers R (which is in fact a total order); • Similarly, the “greater than or equal to” relation, denoted by ≥, on the set of real numbers R; • R= {(a,b) ∣a,b∈Z,a=b+1}; • “a is an ancestor of b” is a partial order relation on the set of all people (provided each person is an ancestor of himself/herself); • The set of events in special relativity is described by a partial order. An event b can only be casually affected by an event a, if a≼b and both the events are in the future light cone. Example 1: Which of these relations on the set A={1,2,3,4} are partial orders? 1. R1= {(1,1), (1,2), (1,4), (2,2), (2,4), (3,3), (4,4)}. 2. R2= {(1,1), (1,3), (2,1), (2,2), (3,3), (3,4)}, (4,2), (4,4)}. 3. R3= {(1,1), (1,3), (1,4), (2,2), (3,2), (3,4), (4,4)} 4. R4= {(1,1), (2,2), (2,3), (2,4), (3,2), (3,3)}, (3,4), (4,3), (4,4)}. Solution. 1. R1 is a partial order since it is reflexive, antisymmetric, and transitive. 2. R2 is not transitive: (1,3), (3,4) ∈R2, but (1,4) ∉R2. Hence, R2 is not a partial order. 3. R3 is reflexive, antisymmetric, and transitive, so it is a partial order. 4. R4 is not antisymmetric since (2,3) ∈R4 and (3,2) ∈R4. This means that R4 is not a partial order. Example 2:Suppose R is a partial order on a set A. Prove that R−1 is also a partial order. Solution. Since R is reflexive, we have (a,a)∈R for all a∈A. By interchanging the first and second element, we obtain the same identity pair (a,a)∈R. Hence, (a,a)∈R−1, so the relation R−1 is also reflexive. 67 CU IDOL SELF LEARNING MATERIAL (SLM)

The original relation R is antisymmetric: If(a,b)∈R and(b,a)∈R,then a=b. Using the definition of R−1, we can replace here (a,b)∈R with (b,a)∈R−1 and (b,a)∈R with (a,b)∈R−1. Then the previous statement is written as If(b,a)∈R−1 and(a,b)∈R−1,then a=b, which means that the inverse relation R−1 is antisymmetric. Suppose that (a,b)∈R−1 and (b,c)∈R−1. By definition of R−1, we can write (b,a)∈R and(c,b)∈R. Since R is transitive, we have (c,a)∈R,⇒(a,c)∈R−1. This proves the transitivity of R−1. Thus, the inverse relation R−1 is a partial order. 3.9 SUMMARY Relation is a subset of the Cartesian product. Or simply, a bunch of points (ordered pairs). In other words, the relation between the two sets is defined as the collection of the ordered pair, in which the ordered pair is formed by the object from each set. A relation is said to be discrete if there are a finite number of data points on its graph. Graphs of discrete relations appear as dots. A relation is said to be continuous if its graph is an unbroken curve with no \"holes\" or \"gaps.\" A relation between two sets is a collection of ordered pairs containing one object from each set. A connection between the elements of two or more sets is Relation. The sets must be non-empty. A subset of the Cartesian product also forms a relation R. Representation of Relation: xRy makes sense for x ϵ A and y ϵ B. Domain of R: The domain of R is the set of first coordinates in R Range of R: The range of R is the set of second coordinates in R Types of Relations Empty Relation: A relation R in a set X, is called an empty relation, if no element of X is related to any element of X, i.e., R = Φ ⊂ X × X 68 CU IDOL SELF LEARNING MATERIAL (SLM)

Universal Relation: A relation R in a set X, is called universal relation, if each element of X is related to every element of X, i.e., R = X × X Reflexive Relation: A relation R defined on a set A is said to be reflexive, if (x, x) ∈ R, ∀ x ∈ A or xRx, ∀ x ∈ R Symmetric Relation: A relation R defined on a set A is said to be symmetric, if (x, y) ∈ R ⇒ (y, x) ∈ R, ∀ x, y ∈ A or xRy ⇒ yRx, ∀ x, y ∈ R. Transitive Relation: A relation R defined on a set A is said to be transitive, if (x, y) ∈ R and (y, z) ∈ R ⇒ (x, z) ∈ R, ∀ x, y, z ∈ A or xRy, yRz ⇒ xRz, ∀ x, y, z∈ R. Equivalence Relation: A relation R defined on a set A is said to be an equivalence relation if R is reflexive, symmetric and transitive. Important properties for a relation R on a set A R is reflexive if xRx for all x. R is symmetric if xRy→yRx for all x, y. R is transitive if xRy and yRz→xRz for all x, y, z. Composition of Relation: • Let R be the relation from A to B & S a relation from B to C. • The composition of R and S is denoted by R ∙ S / RS is the relation from A to C which is given by a RS c if there is an element b ϵ B such that a R b and b S c Partial Order Relation: A binary relation R on a non-empty set A is called a (non-strict) partial order relation or partial ordering if and only if the relation is • reflexive • antisymmetric, and • transitive. 69 CU IDOL SELF LEARNING MATERIAL (SLM)

3.10 KEYWORDS • Relation: A relation is a correspondence between two sets • Ordered Pair: An ordered pair is a composition of the x coordinate (abscissa) and the y coordinate (ordinate), having two values written in a fixed order within parentheses • Partial Order Relation: A binary relation R on a non-empty set A is called a (non-strict) partial order relation or partial ordering if and only if the relation is • reflexive • antisymmetric, and • Transitive. • Transitive Relation: A binary relation R on a set A is called transitive if for all a,b,c∈A it holds that if aRb and bRc, then aRc. • Symmetric Relation: A binary relation R on a set A is called symmetric if for all a,b∈A it holds that if aRb then bRa 3.11 LEARNING ACTIVITY 1. Let R1 be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R2 be another relation from B to C = {1, 2, 3, 4} as defined below: i. An element a in A is related to an element b in B (under R1) if a * b is divisible by 3. ii. An element a in B is related to an element b in C (under R2) if a * b is even but not divisible by 3. Which is the composite relation R1R2 from A to C? 2. An electrician charges a base fee of Rs.70 plus Rs.50 for each hour of work. Create a table that shows the amount the electrician charges for 1, 2, 3, and 4 hours of work. Let x represent the number of hours and y represent the amount charged for x hours. Is this relation a function? 3.12 UNIT END QUESTIONS 70 A. Descriptive Type Questions 1. Write the domain and range of the following relations. (a) R₁ = {(4, 3); (6, 8); (4, 8); (0, 9); (7, 5); (0, 10)} CU IDOL SELF LEARNING MATERIAL (SLM)

2.Let P={1,2,3,.....,18}P={1,2,3, ....,18} Definerelation Rr From Pp To Pp By R={(X,Y):2x−Y=0,Wh erex,Y∈P}R={(X,Y):2x−Y=0,Wherex,Y∈P} Write Down Its Domain, Co-Domain andRange. Draw the Arrow Diagram for the Relation Also 3. Adjoining figure shows a relationship between the set A and B. Write this relation in the roster form. What is its domain and range? Fig 3.12: Relation between A and B for example 3 4. Draw the arrow diagrams to represent the following relations. (a) R₁ = {(3, 3); (3, 6); (3, 9); (5, 8); (6, 3)} (b) R₂ = {(4, 10); (4, 13); (4, 16); (5, 13); (6, 16)} (c) R₃ = {(2, 3); (3, 5); (4, 7); (5, 9); (6, 11)} (d) R₄ = {(p, l); (p, m); (q, x); (q, n); (r, m)} 5. Explain Equivalence Relation B. Multiple Choice Questions: 1. Let A and B be two non-empty relations on a set S. Which of the following statements is false? a) A and B are transitive ⇒ A∩B is transitive b) A and B are symmetric ⇒ A������B is symmetric c) A and B are transitive ⇒ A������B is not transitive d) A and B are reflexive ⇒ A∩B is reflexive 2. Determine the characteristics of the relation aRb if a2 = b2. a) Transitive and symmetric b) Reflexive and asymmetry 71 CU IDOL SELF LEARNING MATERIAL (SLM)

c) Trichotomy, anti-symmetry, and irreflexive d) Symmetric, Reflexive, and transitive 3. The less-than relation, <, on a set of real numbers is a) not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric b) a partial ordering since it is asymmetric and reflexive c) a partial ordering since it is antisymmetric and reflexive d) not a partial ordering because it is not antisymmetric and reflexive 4. The less-than relation, <, on a set of real numbers is a) not a partial ordering because it is not asymmetric and irreflexive equals antisymmetric b) a partial ordering since it is asymmetric and reflexive c) a partial ordering since it is antisymmetric and reflexive d) not a partial ordering because it is not antisymmetric and reflexive 5. Suppose X = {a, b, c, d} and π1 is the partition of X, π1 = {{a, b, c}, d}. The number of ordered pairs of the equivalence relations induced by a) 15 b) 10 c) 34 d) 5 6. A partial order P is defined on the set of natural numbers as follows. Here a/b denotes integer division. i) (0, 0) ∊ P. ii) (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P. Consider the following ordered pairs: i. (101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153) The ordered pairs of natural numbers are contained in P are and a) (145, 265) and (0, 153) b) (22, 101) and (0, 153) c) (101, 22) and (145, 265) d) (101, 22) and (0, 153 7. Suppose a relation R = {(3, 3), (5, 5), (5, 3), (5, 5), (6, 6)} on S = {3, 5, 6}. Here R is known as a) equivalence relation b) reflexive relation 72 CU IDOL SELF LEARNING MATERIAL (SLM)

c) symmetric relation d) transitive relation 8. Which of the following relations is the reflexive relation over the set {1, 2, 3, 4}? a) {(0,0), (1,1), (2,2), (2,3)} b) {(1,1), (1,2), (2,2), (3,3), (4,3), (4,4)} c) {(1,1), (1,2), (2,1), (2,3), (3,4)} d) {(0,1), (1,1), (2,3), (2,2), (3,4), (3,1) 9. For a, b ∈ Z define a | b to mean that a divides b is a relation which does not satisfy a) irreflexive and symmetric relation b) reflexive relation and symmetric relation c) transitive relation d) symmetric relation 10. Which of the following is an equivalence relation on R, for a, b ∈ Z? a) (a-b) ∈ Z b) (a2+c) ∈ Z c) (ab+cd)/2 ∈ Z d) (2c3)/3 ∈ Z Answers: 1-c; 2-d; 3 - a; 4 -c; 5 -b;6 – d; 7 – a; 8 – b; 9 – b; 10 – b; 3.13 REFERENCES • Kenneth Rosen, Discrete Mathematics and Its Applications with Combinatorics and Graph Theory (SIE) | 7th Edition, McGraw Hill Education; 7 editions. • Susanna S. Epp, Discrete Mathematics with Applications, Cengage Learning • Seymour Lipschutz, Marc Lara’sLipson, Varsha H. Patil, Discrete Mathematics (Schaum's Outlines) Revised 3rd Edition, McGraw Hill Education; Revised Third edition. • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond (Undergraduate Texts in Mathematics), Springer • Miklos Bona Introduction to Enumerative and Analytic Combinatorics (Discrete Mathematics and Its Applications) 2nd Edition, Chapman and Hall/CRC 73 CU IDOL SELF LEARNING MATERIAL (SLM)

• Harry Lewis, Rachel Zax, Essential Discrete Mathematics for Computer Science, Princeton University Press • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 74 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 4 - FUNCTIONS Structure 4.0. Learning Objectives 4.1. Introduction 4.2. Definition 4.3. Types of function, 4.4. Composition of functions, 4.5. Recursively defined functions. 4.6. Summary 4.7. Key Words/Abbreviations 4.8. Learning Activity 4.9. Unit End Questions (MCQ and Descriptive) 4.10.References 4.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • Explain the concept of Functions • Enumerate the types and Composition of functions, • Comprehend the Recursively defined functions. 4.1 INTRODUCTION Function, in mathematics, an expression, rule, or law that defines a relationship between one variable (the independent variable) and another variable (the dependent variable). Functions are ubiquitous in mathematics and are essential for formulating physical relationships in the sciences. The modern definition of function was first given in 1837 by the German mathematician Peter Dirichlet - If a variable y is so related to a variable x that whenever a numerical value is assigned to x, there is a rule according to which a unique value of y is determined, then y is said to be a function of the independent variable x. A Function assigns to each element of a set, exactly one element of a related set. Functions find their application in various fields like representation of the computational complexity of algorithms, counting objects, study of sequences and strings, to name a few. There are different types of functions which are given below: 1. One-one Function (or Injective Function) 2. Many-One Function 75 CU IDOL SELF LEARNING MATERIAL (SLM)

3. Onto Function (Surjective Function) 4. One-One onto Function (Bijective Function) 4.2 DEFINITION A function or mapping (Defined as f:X→Y) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function ‘f’. Function ‘f’ is a relation on X and Y such that for each x ∈ X, there exists a unique y ∈ Y such that (x, y) ∈ R. ‘x’ is called pre-image and ‘y’ is called image of function f. A function can be one to one or many to one but not one to many. The synonyms of “function” are “mapping”, “transformation”, “correspondence” and operator. Other Way to understand ‘Function’: Let A& B be the two non-empty sets. Now a function ƒ: A→ B is a relation from A to B such that: • Dom ƒ = A, for each a ϵ A, (a, b) ∈ƒ for some b ϵ B which refers that ƒ is defined at each a ∈ A. • If (a, b) ∈ƒ and (a, c) ∈ƒ then b = c. In this, we can refer ƒ is well defined or single valued. Thus, no element of A is related to two elements of B • If (a, b)∈ƒ then b is known as the image of a under ƒ& we can represent it in the following wayb = ƒ(a) Example 1:Find out if R is a mapping/function from A to B. (i) Let A = {3, 4, 5} and B= {6, 7, 8, 9} and R = {(3, 6) (4, 7) (5, 8)} Solution: Since, R = {(3, 6); (4, 7); (5, 8)} then Domain (R) = {3, 4, 5} = A We observe that no two ordered pairs in R have the same first component. Therefore, R is a mapping/function from A to B. Example 2: Let A = {1, 2, 3} and B= {7, 11} and R = {(1, 7); (1, 11); (2, 11); (3, 11)} Solution: Since, R = {(1, 7); (1, 11); (2, 11); (3, 11)} then Domain (R) = {1, 2, 3} = A But the ordered pairs (1, 7) (1, 11) have the same first component. Therefore, R is not a mapping/function from A to B. 76 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 3: Let X = {x, y, z, k} and Y = {1, 2, 3, 4}. Determine which of the following functions. Give reasons if it is not. Find range if it is a function. a. f = {(x, 1), (y, 2), (z, 3), (k, 4) b. g = {(x, 1), (y, 1), (k, 4) c. h = {(x, 1), (x, 2), (x, 3), (x, 4) d. l = {(x, 1), (y, 1), (z, 1), (k, 1)} e. d = {(x, 1), (y, 2), (y, 3), (z, 4), (z, 4)}. Solution: 1. It is a function. Range (f) = {1, 2, 3, 4} 2. It is not a function because every element of X does not relate with some element of Y i.e., Z is not related with any element of Y. 3. h is not a function because h (x) = {1, 2, 3, 4} i.e., element x has more than one image in set Y. 4. d is not a function because d (y) = {2, 3} i.e., element y has more than image in set Y. Example 4: Find out if R is a mapping from A to B. (i) Let A = {3, 4, 5} and B= {6, 7, 8, 9} and R = {(3, 6) (4, 7) (5, 8)} Solution: Since, R = {(3, 6); (4, 7); (5, 8)} then Domain (R) = {3, 4, 5} = A We observe that no two ordered pairs in R have the same first component. Therefore, R is a mapping from A to B. (ii) Let A = {1, 2, 3} and B= {7, 11} and R = {(1, 7); (1, 11); (2, 11); (3, 11)} Solution: Since, R = {(1, 7); (1, 11); (2, 11); (3, 11)} then Domain (R) = {1, 2, 3} = A But the ordered pairs (1, 7) (1, 11) have the same first component. 77 CU IDOL SELF LEARNING MATERIAL (SLM)

Therefore, R is not a mapping from A to B. Example 5:Let f be a function defined on ℤ (the set of all integers), such that f(x)=x2. Find the domain and the range of f. Solution: The domain of f has already been stated in the question: the set of all integers, ℤ. Now, any integer when squared will generated a positive perfect square. Thus, the set of output values will be these. 0,1,4,9,16, … We can thus say that the range is the set of all positive perfect squares. We can write this as follows: R=n2,n in ℤ Note that since the domain is discrete, the range is also discrete Representationof a function by an arrow diagram: In this, we represent the sets by closed figures and the elements are represented by points in the closed figure. The mapping f: A → B is represented by arrow which originates from elements of A and terminates at the elements of B. Fig 4.1: Mapping f: A → B 78 Example 6: Let A = {1, 2, 3, 4} and B = {0, 3, 6, 8, 12, 15} Consider a rule f (x) = x² - 1, x∈A, then (a) show that f is a mapping from A to B. (b) draw the arrow diagram to represent the mapping. (c) represent the mapping in the roster form. CU IDOL SELF LEARNING MATERIAL (SLM)

(d) write the domain and range of the mapping. Solution: (a) Using f (x) = x² - 1, x ∈ A we have f (1) = 0, f (2) = 3, f (3) = 8, f (4) = 15 We observe that every element in set A has unique image in set B. Therefore, f is a mapping from A to B. (b) Arrow diagram which represents the mapping is given below. Fig 4.2: Solution of (b) representing mapping from A to B 79 (c) Mapping can be represented in the roster form as f = {(1, 0); (2, 3); (3, 8); (4, 15)} (d) Domain (f) = {1, 2, 3, 4} Range (f) = {0, 3, 8, 15} 4.3 TYPES OF FUNCTION ONE-TO-ONE FUNCTION: If a function saysƒ: A→ B satisfies the following condition below: • ƒ (x1) = y and ƒ (x2) = y implies x1 = x2 • For each b ∈Range ƒ, f−1(b) contains only one element. • Let f−1(b) as the set of preimages of b, for each b ϵ ran ƒ, b has precisely one preimage ONTO FUNCTION: If a function says ƒ = A→ B satisfies the following condition below: • Rangeƒ= B or • f−1(b) is non empty for each b ϵ B • For each b ϵ B has some preimage in A INVERSE FUNCTION: CU IDOL SELF LEARNING MATERIAL (SLM)

Let a functionƒ: A→ B is one-to-one and onto function, then the inverse relation ƒ-1is single valued, & thus is a function from B to A. In this case ƒ-1is the inverse function of ƒ. Note: • A one to one & onto functionƒ: A→ B is also known as one-to-one correspondence between A&B • If a functionƒ: A→ B is not one-to-one then it is called as many-to-one function. Also, if ƒ not onto B then it is known as into B • Two functions are equal if they are equal as a set because function is also a set Examples: • Let A = {r, s, t}, B = {1, 2, 3} and C = {r, s, t, u}. So, R= {(r, 1), (r, 2), (t, 2)} is a relation from A to B but R is not a function since R (r) = {1,2} • The set ƒ = {(r, 1), (s, 2), (t, 2)} is a function from A to B but ƒ is not one-to-one since ƒ-1(2) = {s, t} & also ƒ is not onto B as ƒ-1(3) = ϕ • The function g = {(r, 1), (s, 2), (t, 3)} is both one-to-one & onto function from A to B. Also,g-1 = {(1, r), (2, s), (3, t)} • The function h: C → B defined as h= {(r, 1), (s, 1), (t, 2), (u, 3) is onto but not one-to-one function since h-1(1) = {r, s-1} HASH FUNCTION: Suppose we wish to retrieve some information stored in a table of size n with indexes 0, 1 . . . n – 1. The items in the table can be very general things. For example, the items might be strings of letters, or they might be large records with many fields of information. To look up a table item we need a key to the information we desire. For example, if the table contains records of information for the 12 months of the year, the keys might be the three-letter abbreviations for the 12 months. To look up the record for January, we would present the key Jan to a lookup program. The program uses the key to find the table entry for the January record of information. Then the information would be available to us. An easy way to look up the January record is to search the table until the key Jan is found. This might be OK for a small table with 12 entries. But it may be impossibly slow for large tables with thousands of entries. Here is the general problem that we want to solve.Given a key, find the table entry containing the key without searching. This may seem impossible at first glance. But let’s consider away to use a function to map each key directly to its table location. We can define hash function is a function that maps a set S of keys toa finite set of table indexes, which we’ll assume are 0, 1 ... n – 1. A table whose information found by a hash function called a hash table. 80 CU IDOL SELF LEARNING MATERIAL (SLM)

For example, let S be the set of three-letter abbreviations for the months of the year. We might define a hash function f: S → {0, 1 ... 11} in the following way. f (XYZ) = (ord (X) + ord (Y) + ord (Z)) mod 12. where ord (X) denotes the integer value of the ASCII code for X. (The ASCII values for A to Z and a to z are 65 to 90 and 97 to 122, respectively.) For example, we’ll compute the value for the key Jan. f(JAN) = [ord(X) + ord (Y) + ord(n)] mod 12 = (74+97+110) mod 12 = 5. CHARACTERISTICS FUNCTION: Consider some universal set ‘U’. Let A ⊆ U. The function χA: U → {0,1}definedby χA(x) = 1, ifx ∈ A χA(x) = 0, ifx ∈ Acis called the characteristic function of A 4.4 COMPOSITION OF A FUNCTION Let f be a function from set A to set B and let g be a function from set B to set C. The composition of the functions g and f, denoted by g ∘ f is defined by (g ∘ f) (a) = g (f (a)) Example 1: Let A = {1, 2, 3} and B = {a, b, c, d}. Then g: A ⟶A f: A⟶B 1⟶3 1⟶ b 2⟶1 2⟶a 3⟶2 3⟶d So, the composition of function is given as f ∘ g: A⟶B 1⟶d 2⟶b 3⟶a 2. (f ∘ f)(x)and(f −1 ∘ f)(x) = x, forallx. Let f: R⟶R, where f(x) = 2x – 1 and f−1(x) = (x + 1)⁄2 (f−1 ∘ f)(x) = f[f −1(x)] 81 CU IDOL SELF LEARNING MATERIAL (SLM)

= f[ (x + 1)⁄2] x+1 = 2[ 2 ]−1 = (x + 1) − 1 =x Example 3: Consider f, g and h, all functions on the integers, by f (n) =n2, g (n) = n + 1 and h (n) = n - 1. Determine (i) h∘f∘g (ii) g∘f∘h (iii) f∘g∘h. Solution: (i) h∘f∘g (n) = n + 1, h∘f∘g (n + 1) = (n+1)2 h [(n+1)2] = (n+1)2 - 1 = n2 + 1 + 2n - 1 = n2 + 2n. (ii) g∘f∘h (n) = n - 1, gof (n - 1) = (n-1)2 82 g [(n-1)2] = (n-1)2 + 1 = n2 + 1 - 2n + 1 = n2 - 2n + 2. (iii) f∘g∘h (n) = n – 1 f∘g (n - 1) = (n - 1) + 1 f (n) = n2. • If f and g are one-to-one, then the function (g∘f) is also one-to-one. • If f and g are onto then the function (g∘f) is also onto. CU IDOL SELF LEARNING MATERIAL (SLM)

• Composition consistently holds associative property but does not hold commutative property. 4.5 RECURSIVELY DEFINED FUNCTIONS Most of the functions we have dealt with in previous chapters have been defined explicitly: by a formula in terms of the variable. We can also define functions recursively: in terms of the same function of a smaller variable. In this way, a recursive function \"builds\" on itself. A recursive definition has two parts: 1. Definition of the smallest argument (usually f (0) or f (1)). 2. Definition of f (n), given f (n - 1), f (n - 2), etc. Here is an example of a recursively defined function: We can calculate the values of this function: This recursively defined function is equivalent to the explicitly defined function f (n) = 2n + 5. However, the recursive function is defined only for nonnegative integers. Here is another example of a recursively defined function: The values of this function are: 83 CU IDOL SELF LEARNING MATERIAL (SLM)

This recursively defined function is equivalent to the explicitly defined function f (n) = n2. Again, the recursive function is defined only for nonnegative integers. Here is one more example of a recursively defined function: The values of this function are: This is the recursive definition of the factorial function, F(n) = n! Not all recursively defined functions have an explicit definition. THE FIBONACCI NUMBERS One special recursively defined function, which has no simple explicit definition, yields the Fibonacci numbers: The values of this function are: Thus, the sequence of Fibonacci numbers is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …. 84 CU IDOL SELF LEARNING MATERIAL (SLM)

4.6 SUMMARY Many widely used mathematical formulas are expressions of known functions. For example, the formula for the area of a circle, A = πr2, gives the dependent variable A (the area) as a function of the independent variable r (the radius). Functions involving more than two variables also are common in mathematics, as can be seen in the formula for the area of a triangle, A = bh/2, which defines A as a function of both b (base) and h (height). In these examples, physical constraints force the independent variables to be positive numbers. When the independent variables are also allowed to take on negative values—thus, any real number—the functions are known as real-valued functions. A function or mapping (Defined as f:X→Y) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function ‘f’. Function ‘f’ is a relation on X and Y such that for each x ∈ X, there exists a unique y ∈ Y such that (x, y) ∈ R. ‘x’ is called pre-image and ‘y’ is called image of function f. A function can be one to one or many to one but not one to many. Injective / One-to-one function: A function f: A→B is injective or one-to-one function if for every b∈B, there exists at most one a∈A such that f(s)=t. This means a function f is injective if a1≠a2 implies f(a1) ≠f(a2). Surjective / Onto function: A function f: A→B is surjective (onto) if the image of f equals its range. Equivalently, for every b∈B, there exists some a ∈ A such that f(a)=bf(a)=b. This means that for any y in B, there exists some x in A such that y=f(x). Bijective / One-to-one Correspondent: A function f: A→B is bijective or one-to-one correspondent if and only if f is both injective and surjective. Inverse of a Function: The inverse of a one-to-one corresponding function f: A→B, is the function g: B→A, holding the following property – f(x)=y⇔g(y)= x The function f is called invertible, if its inverse function g exists. Composition of Functions: Two functions f: A→B and g: B→C can be composed to give a 85 composition g ∘f. This is a function from A to C defined by (g ∘ f) (x)=g(f(x)) Some Facts about Composition CU IDOL SELF LEARNING MATERIAL (SLM)

• If f and g are one-to-one then the function (g∘f) (g∘f) is also one-to-one. • If f and g are onto then the function (g∘f) (g∘f) is also onto. • Composition always holds associative property but does not hold commutative property. 4.7 KEYWORDS • Functions: A function or mapping (Defined as f:X→Y) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets) • Domain: The set of all inputs for a function is called the domain • Co-Domain: The set of all allowable outputs is called the codomain • Recursive function: in logic and mathematics, a type of function or expression predicating some concept or property of one or more variables, which is specified by a procedure that yields values or instances of that function by repeatedly applying a given relation or routine operation to known values of the function. • A hash function: is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. 4.8 LEARNING ACTIVITY 1. Explain different types of function with representation and consider the example of teachers and student in the class. 2. Identify the independent and dependent variables. Write a rule in function notation for the situation. a. A math tutor charges Rs.35 per hour. b. A fitness centre charges a Rs.100 initiation fee plus $40 per month. c. Stephen buys lettuce that costs Rs.1.69/lb. 4.9 UNIT END QUESTIONS A. Descriptive Questions 1. Let N be the set of natural number if f: N → N by f (x) = 3x +2, then find f (1), f (2), f (-3), f (-4). 86 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Explain Hash Function 3. Discuss Inverse Function 4. What is Composition of Function? 5. Let A = {a, b, c, d} and B= {c, d, e, f, g}, Let R₁ = {(a, c) (b, d) (c, e)} R₂ = {(a, c) (a, g) (b, d) (c, e) (d, f)} R₃ = {(a, c) (b, d) (c, e) (d, f)} Justify which of the given relation is a function from A to B. B. Multiple Choice Questions if and only if f(a) = f(b) implies that a = b for all a and b 1. A function is said to be in the domain of f. a) One-to-many b) One-to-one c) Many-to-many d) Many-to-one 2. Which of the following function f: Z X Z → Z is not onto? a) f (a, b) = a + b b) f (a, b) = a c) f (a, b) = |b| d) f (a, b) = a – b 3. Which of the following function f: Z X Z → Z is not onto? a) f (a, b) = a + b b) f (a, b) = a c) f (a, b) = |b| d) f (a, b) = a – b 4. Let f and g be the function from the set of integers to itself, defined by f(x) = 2x + 1 and g(x) = 3x + 4. Then the composition of f and g is a) 6x + 9 b) 6x + 7 c) 6x + 6 d) 6x + 8 87 CU IDOL SELF LEARNING MATERIAL (SLM)

5. The inverse of function f(x) = x3 + 2 is a) f -1 (y) = (y – 2) 1/2 b) f -1 (y) = (y – 2) 1/3 c) f -1 (y) = (y) 1/3 d) f -1 (y) = (y – 2) 6. Let f and g be the function from the set of integers to itself, defined by f(x) = 2x + 1 and g(x) = 3x + 4. Then the composition of f and g is a) 6x + 9 b) 6x + 7 c) 6x + 6 d) 6x + 8 7. The inverse of function f(x) = x3 + 2 is a) f -1 (y) = (y – 2) 1/2 b) f -1 (y) = (y – 2) 1/3 c) f -1 (y) = (y) 1/3 d) f -1 (y) = (y – 2) 8. What is the domain of a function? a) the maximal set of numbers for which a function is defined b) the maximal set of numbers which a function can take values c) it is a set of natural numbers for which a function is defined d) none of the mentioned 9. What is the range of a function? a) the maximal set of numbers for which a function is defined b) the maximal set of numbers which a function can take values c) it is set of natural numbers for which a function is defined d) none of the mentioned 10. If f(x) = x2 + 4 then range of f(x) is given by? 88 a) [4, ∞) b) (-∞, ∞) – {0} CU IDOL SELF LEARNING MATERIAL (SLM)

c) (0, ∞) d) None of the mentioned Answers: 1- b; 2 – c; 3 – d; 4 – a; 5 – b; 6 – a; 7 – b; 8 – a; 9 – b; 10 – a; 4.10 REFERENCES • Kenneth Rosen, Discrete Mathematics and Its Applications with Combinatorics and Graph Theory (SIE) | 7th Edition, McGraw Hill Education; 7 editions • Jean-Paul Tremblay, R Manohar, DISCRETE MATHEMATICAL STRUCTURES WITH APPLICATIONS TO COMPUTER SCIENCE, McGraw Hill Education; 1st edition • Susanna S. Epp, Discrete Mathematics with Applications, Cengage Learning • C Liu, D. Mohapatra, Elements of Discrete Mathematics: A Computer Oriented Approach | 4th Edition, McGraw Hill Education • V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc • Miklos Bona Introduction to Enumerative and Analytic Combinatorics (Discrete Mathematics and Its Applications) 2nd Edition, Chapman and Hall/CRC • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 89 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 5- COMBINATORICS 1 Structure 5.0. Learning Objectives 5.1. Introduction 5.2. Mathematical induction 5.3. Recursive mathematical definitions 5.3.1 The Recursion Theorem: 5.3.2 Strong Mathematical Induction: 5.4. Basics of counting 5.4.1 Sum Rule: (The principle of disjunctive Counting) 5.4.2 Product Rule: (The principle of sequential counting) 5.4.3 Indirect Counting: 5.5. Summary 5.6. Keywords 5.7. Learning Activity 5.8. Self-Assessment Questions 5.9. References 5.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • Explain the basics of Combinatorics • State the Mathematical induction • Enumerate the Basics of counting 5.1 INTRODUCTION Combinatorics, also called combinatorial mathematics, the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. Included is the closely related area of combinatorial geometry. We shall learn about the various properties of mathematical inductions that form the basis of theoretical maths. The principle of mathematical induction is used in algebra or other streams of mathematics that involve the formulation of results or statements in terms of “n”. To prove the basic principle behind ‘n’, which is a positive integer, we use a set of well-established and well-suited principles in a specific format. The techniques used to prove statements with regard to “n” are known as principles of mathematical 90 CU IDOL SELF LEARNING MATERIAL (SLM)

induction. One key basis for mathematical thinking is deductive reasoning. Let us consider the following example of deductive reasoning (a) Socrates is a man. (b) All men are mortal, therefore, (c) Socrates is mortal. So, when statements (a) and (b) are true, then (c) is also true. Similarly, we have another example (i) Eight is divisible by two. (ii) Any number divisible by two is an even number, therefore, (iii) Eight is an even number. Thus, deduction in a nutshell is given a statement to be proven, often called a conjecture or a theorem in mathematics, valid deductive steps are derived and a proof may or may not be established, i.e., deduction is the application of a general case to a particular case. Opposite to deduction, inductive reasoning depends on working with each case, and developing a conjecture by observing incidences till we have observed each and every case. It is frequently used in mathematics and is a key aspect of scientific reasoning, where collecting and analysing data is the norm. Thus, in simple language, we can say the word induction means the generalisation from particular cases or facts. In algebra or in other discipline of mathematics, there are certain results or statements that are formulated in terms of n, where n is a positive integer. To prove such statements the well-suited principle that is used–based on the specific technique, is known as the principle of mathematical induction. 5.2 MATHEMATICAL INDUCTION: • The inductive aspect of mathematics is concerned with the search for facts by observation and experimentation • We arrive at conjecture (reasoning that involves the formation of conclusions from incomplete evidence) for a general rule by inductive reasoning PRINCIPLE OF MATHEMATICAL INDUCTION: 91 CU IDOL SELF LEARNING MATERIAL (SLM)

In a simple way, Mathematical induction is a special way of proving things. In this system, we try to show it is true for one thing and then it is true for other things and finally, true for all things. Like Domino Effect. If First Domino Falls Then the Next One Falls and So…. All Dominos Will Fall Let P(n) be a statement which, for each integer n, may be either true or false. To prove P(n) is true for all integers n ≥ 1, it is sufficient to prove the following 1. P (1) is true 2. For all k ≥ 1, P(k) implies P (k + 1) If we replace first step by P (n0) is true, and second step by ‘for all k ≥ n0, P (k) implies P (k + 1), Then we can prove P (n) is true for all n ≥ n0, and the starting point n0 – is the basis of induction which may be an integer, positive, negative or zero. To prove P (k) →P (k + 1) we use following 3 steps: a. Show P (n0) is true (Basis of Induction) b. Assume P (k) is true for k ≥ n0 (Inductive Hypothesis) c. Show that P (k + 1) is true on the basis of the inductive hypothesis (Inductive Step) Example 1: 3n – 1 is a multiple of 2 1. Show it is true for n=1 31– 1 = 3 – 1 = 2 Yes 2 is a multiple of 2. 31–1 is true 2. Assume it is true for n=k which means 3k– 1 is true (an assumption) 3. Now we will prove that 3k+1 – 1 is a multiple of 2 We can write 3k+1 as 3×3k n = k caseStep 2 Therefore, 3k+1 – 1 = 3 × 3k – 1 = 2 × 3k +3k – 1 92 CU IDOLMSuEltLipFleLoEfA2RNING MATERIAL (SLM)

As from above we can conclude ✓ 2·3k is a multiple of 2 (you are multiplying by 2) ✓ 3k– 1 is true (we said that in the assumption above) Hence, 3k+1 – 1 is true proved. Example 2: Let us use the above approach on the problem of determining a formula for the sum of the first n positive integers. Let S(n) = 1 + 2 + 3+ … + n. Below find the table where few values of S(n) are listed N1 2 3 4 5 6 7 S(n) 1 3 6 10 15 21 28 Guessing a formula on the basis of above table is quite difficult. Also, we can observe the following pattern as 2 S (1) = 2 = 1. 2 2 S (2) = 6 = 2. 3 2 S (3) = 12 = 3. 4 2 S (4) = 20 = 4. 5 2 S (5) = 30 = 5. 6 2 S (6) = 42 = 6. 7 This leads to conjecture that 93 2 S(n) = n(n + 1)or that S(n) = n(n+1) 2 We will use mathematical induction to prove the above formula. Let P (n) = the sum S (n) of the first n positive integers is equal to n (n +1)/2 1. Basis of Induction: We will consider n =1, S (1) = 1 (1 + 1) / 2 2. Inductive Hypothesis: Assume the statement P (n) is true for n=k, we will have S (k) = 1 + 2 + 3 +… + k = k (k +1) /2 3. Inductive Step: We will prove the formula is true for n=k +1 We can write S(k + 1) = 1 + 2 + 3 + ⋯ + k + (k + 1) = S(k) + (k + 1) CU IDOL SELF LEARNING MATERIAL (SLM)

k = 2 (k + 1) + (k + 1) k = (k + 1) + ( 2 + 1) (k + 1)(k + 2) =2 Thus, formula holds true for k + 1. Example 3: Find and prove a formula for the sum of the first n cubes, that is, 13 + 23 + … + n3 We will first consider following few cases as: 13 = 1 = 12 13 + 23 = 9 = 32 13 + 23 + 33 = 36 = 62 13 + 23 + 33 + 43 = 100 = 102 Till now we are unable to identify any pattern but if we refer the table of S (n) in above example, we can figure out [S (1)]2 = 12 [S (2)]2 = 32 [S (3)]2 = 62 [S (4)]2 = 102 [S (5)]2 = 152 We conjecture that 13 + 23 + … + n3 = [n (n +1) /2]2 Now we will verify this by mathematical induction. 1. Basis for Induction: Since 13 = [ 1 (1+1) /2]2 is true for n = 1 2. Induction Hypothesis: Suppose for n=k the above formula is true, so we have 13 + 23 + … + k3 = [k (k +1) /2]2 3. Inductive Step: Consider n = k + 1 13 + 23 + ⋯ + k3 + (k + 1)3 = [(k + 1)(k + 2)/2]2 From above hypothesis, we can replace 13 + 23 + ⋯ + k3 by [k(k + 1)/2]2 as 13 + 23 + ⋯ + k3 + (k + 1)3is nothing more than the sum of 13 + 23 + ⋯ + k3 and (k + 1)3. k(k + 1) 2 13 + 23 + ⋯ + k3 + (k + 1)3 = [ 2 ] + (k + 1)3 = (k + 1)2 [(2k)2 + k + 1] 94 CU IDOL SELF LEARNING MATERIAL (SLM)

= (k + 1)2 [k2 + k + 1] 4 = (k + 1)2 [ k2 + 4k + 4 ] 4 k+2 = (k + 1)2[ ]2 2 = [(k + 1)(k + 2)]2 2 Hence the formula holds for k +1 and thus by the principle of mathematical induction for all positive integers n. Example 4: Using the principle of mathematical induction, prove that 1² + 2² + 3² +..... + n² = (1/6) {n (n + 1) (2n + 1} for all n ∈ N. Solution: Let the given statement be P(n). Then, P(n): 1² + 2² + 3² + ..... +n² = (1/6) {n (n + 1) (2n + 1)}. Putting n =1 in the given statement, we get LHS = 1² = 1 and RHS = (1/6) × 1 × 2 × (2 × 1 + 1) = 1. Therefore LHS = RHS. Thus, P (1) is true. Let P(k) be true. Then, P(k): 1² + 2² + 3² + ..... + k² = (1/6){k(k + 1)(2k + 1)}. Now, 1² + 2² + 3² + .......... + k² + (k + 1)² = (1/6) {k(k + 1)(2k + 1) + (k + 1)² = (1/6){(k + 1).(k(2k + 1)+6(k + 1))} = (1/6){(k + 1)(2k² + 7k + 6}) = (1/6){(k + 1)(k + 2)(2k + 3)} = 1/6{(k + 1)(k + 1 + 1)[2(k + 1) + 1]} ⇒ P(k + 1): 1² + 2² + 3² + .......+ k² + (k+1) ² = (1/6) {(k + 1) (k + 1 + 1) [2(k + 1) + 1]} ⇒P (k + 1) is true, whenever P(k) is true. 95 CU IDOL SELF LEARNING MATERIAL (SLM)

Thus, P (1) is true and P (k + 1) is true, whenever P(k) is true. Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N. Example 5: By using mathematical induction prove that the given equation is true for all positive integers. 1 x 2 + 3 x 4 + 5 x 6 + …. + (2n - 1) x 2n = n(n+1) (4n−1)3n(n+1) (4n−1)3 Solution: From the statement formula When n = 1, LHS =1 x 2 = 2 RHS = 1(1+1) (4x1−1)31(1+1) (4x1−1)3 = 6363 = 2 Hence it is proved that P (1) is true for the equation. Now we assume that P (k) is true or 1 x 2 + 3 x 4 + 5 x 6 + …. + (2k - 1) x 2k = k(k+1) (4k−1)3k(k+1) (4k−1)3. For P (k + 1) LHS = 1 x 2 + 3 x 4 + 5 x 6 + …. + (2k - 1) x 2k + (2(k + 1) - 1) x 2(k + 1) = k(k+1) (4k−1)3k(k+1) (4k−1)3 + (2(k + 1) - 1) x 2(k + 1) = (k+1)3(k+1)3(4k2 - k + 12 k + 6) = (k+1) (4k2+8k+3k+6)3(k+1) (4k2+8k+3k+6)3 = (k+1) (k+2) (4k+3)3(k+1) (k+2) (4k+3)3 = (k+1) ((k+1) +1) (4(k+1) −1)3(k+1) ((k+1) +1) (4(k+1) −1)3 = RHS for P (k+1) Now it is proved that P (k + 1) is also true for the equation. So, the given statement is true for all positive integers. Example 6: Using the principle of mathematical induction, prove that 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + .....+ n (n + 1) = (1/3) {n (n + 1) (n + 2)}. Solution: 96 Let the given statement be P(n). Then, P(n): 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +......+ n (n + 1) = (1/3) {n (n + 1) (n + 2)}. Thus, the given statement is true for n = 1, i.e., P (1) is true. Let P(k) be true. Then, P(k): 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +......+ k (k + 1) = (1/3) {k (k + 1) (k + 2)}. Now, 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +.. + k (k + 1) + (k + 1) (k + 2) = (1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ........ + k(k + 1)) + (k + 1)(k + 2) = (1/3) k(k + 1)(k + 2) + (k + 1)(k + 2) [using (i)] = (1/3) [k(k + 1)(k + 2) + 3(k + 1)(k + 2) CU IDOL SELF LEARNING MATERIAL (SLM)

= (1/3){(k + 1)(k + 2)(k + 3)} ⇒ P(k + 1): 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +..... + (k + 1)(k + 2) = (1/3){k + 1 )(k + 2)(k +3)} ⇒ P(k + 1) is true, whenever P(k) is true. Thus, P(1) is true and P(k + 1)is true, whenever P(k) is true. Hence, by the principle of mathematical induction, P(n) is true for all values of ∈ N. Example 7. By using mathematical induction prove that the given equation is true for all positive integers. 2 + 4 + 6 + …. + 2n = n(n+1) Solution: From the statement formula When n = 1 or P (1), LHS = 2 RHS =1 × 2 = 2 So, P (1) is true. Now we assume that P (k) is true or 2 + 4 + 6 + …. + 2k = k (k + 1). For P (k + 1), LHS = 2 + 4 + 6 + …. + 2k + 2(k + 1) = k (k + 1) + 2(k + 1) = (k + 1) (k + 2) = (k + 1) ((k + 1) + 1) = RHS for P(k+1) Now it is proved that P(k+1) is also true for the equation. So, the given statement is true for all positive integers. Example 8: Using the principle of mathematical induction, prove that 97 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 + ....+ (2n - 1) (2n + 1) = (1/3) {n (4n² + 6n - 1). Solution: Let the given statement be P(n). Then, P(n): 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 +.......+ (2n - 1) (2n + 1) = (1/3) n (4n² + 6n - 1). When n = 1, LHS = 1 ∙ 3 = 3 and RHS = (1/3) × 1 × (4 × 1² + 6 × 1 - 1) = {(1/3) × 1 × 9} = 3. LHS = RHS. Thus, P (1) is true. Let P(k) be true. Then, P(k): 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 + …. + (2k - 1) (2k + 1) = (1/3) {k (4k² + 6k - 1) ...... (i) Now, 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 +...........+ (2k - 1)(2k + 1) + {2k(k + 1) - 1}{2(k + 1) + 1} CU IDOL SELF LEARNING MATERIAL (SLM)

= {1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 + .................+ (2k - 1)(2k + 1)} + (2k + 1)(2k + 3) = (1/3) k(4k² + 6k - 1) + (2k + 1)(2k + 3) [using (i)] = (1/3) [(4k³ + 6k² - k) + 3(4k² + 8k + 3)] = (1/3)(4k³ + 18k² + 23k + 9) = (1/3){(k + 1)(4k² + 14k + 9)} = (1/3)[k + 1){4k(k + 1) ² + 6(k + 1) - 1}] ⇒ P(k + 1): 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 +...... + (2k + 1) (2k + 3) = (1/3) [(k + 1) {4(k + 1) ² + 6(k + 1) - 1)}] ⇒P (k + 1) is true, whenever P(k) is true. Thus, P (1) is true and P (k + 1) is true, whenever P(k) is true. Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N. Example 9. By using mathematical induction prove that the given equation is true for all positive integers. 2 + 6 + 10 + …. + (4n - 2) = 2n2 Solution: From the statement formula When n = 1 or P (1), LHS = 2 RHS = 2 × 12 = 2 So,P (1) is true. Now we assume that P (k) is true or 2 + 6 + 10 + …... + (4k - 2) = 2k2 For P (k + 1), LHS = 2 + 6 + 10 + …. + (4k - 2) + (4(k + 1) - 2) = 2k2 + (4k + 4 - 2) = 2k2 + 4k + 2 = (k+1)2 = RHS for P(k+1) Now it is proved that P(k+1) is also true for the equation. So, the given statement is true for all positive integers. Example 10: Using the principle of mathematical induction, prove that 98 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ......+ 1/{n(n + 1)} = n/(n + 1) Solution: Let the given statement be P(n). Then, P(n): 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ...... + 1/{n(n + 1)} = n/(n + 1). Putting n = 1 in the given statement, we get CU IDOL SELF LEARNING MATERIAL (SLM)

LHS= 1/(1 ∙ 2) = and RHS = 1/(1 + 1) = 1/2. LHS = RHS. Thus, P(1) is true. Let P(k) be true. Then, P(k): 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ..... + 1/{k(k + 1)} = k/(k + 1) ..…(i) Now 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ......+ 1/{k(k + 1)} + 1/{(k + 1)(k + 2)} [1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ...... + 1/{k(k + 1)}] + 1/{(k + 1)(k + 2)} = k/(k + 1)+1/{ (k + 1)(k + 2)}. {k(k + 2) + 1}/{(k + 1)²/[(k + 1)k + 2)] using …(ii) = {k(k + 2) + 1}/{(k + 1)(k + 2} = {(k + 1)² }/{(k + 1)(k + 2)} = (k + 1)/(k + 2) = (k + 1)/(k + 1 + 1) ⇒ P(k + 1): 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) +..............+ 1/{ k(k + 1)} + 1/{(k + 1)(k + 2)} = (k + 1)/(k + 1 + 1) ⇒ P(k + 1) is true, whenever P(k) is true. Thus, P(1) is true and P(k + 1)is true, whenever P(k) is true. Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N. 5.3 RECURSIVE MATHEMATICAL DEFINITION: Sometimes it is difficult to define a function or object explicitly; it is easier to define the function or object in terms of the function or object itself. This process is called recursion. Example 1. The Fibonacci Numbers {Fn}, defined by F1 = 1, F2 = 1, Fn = Fn−1 + Fn−2. Recursively Defined Functions: When we define a sequence recursively by specifying how terms of the sequence are found from previous terms, we can use induction to prove results about the sequence. Note that a sequence is basically a function on N. Definition 1. A recursively defined function f with domain N is a function defined by: 1. BASIS STEP: Specify the value of the function at zero. 2. RECURSIVE STEP: Give a rule for finding its value at an integer from its values at smaller integers. Such a definition is called a recursive or inductive definition. Example 2. Give a recursive definition of the sequence {an}, n = 1, 2, 3, . . ., if 1. an = 4n 99 CU IDOL SELF LEARNING MATERIAL (SLM)