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

2. an = 4n 3. an = 4 Solution. There may be more than one correct answer to each sequence. Following are examples for solutions. 1. Since each term in the sequence is 4 greater than the previous term, we may define the sequence by setting a1 = 4 and declaring that an+1 = 4 + an for all n ≥ 1. 2. Each term is 4 times its predecessor. Thus we have a1 = 4 and an+1 = 4an for all n ≥ 1. 3. We may just set a1 = 4 and declare that an+1 = an for all n ≥ 1. 5.3.1 The Recursion Theorem: Let F be a given function from a set S into S. Let s0 be a fixed element of S, and let N denote the set of non-negative integers. Then there is a unique function ƒ: N → S satisfying a. ƒ (0) = s0 b. ƒ (n + 1) = F (ƒ(n) for all integers n ϵ N • The first condition of the Recursion Theorem is called the initial condition and Second condition is called the recurrence relation or generating rule. • Both the parts are necessary for conclusion of the theorem. Example 3: Let us see how to apply the Recursion Theorem a. h (0) = 9 b. h (n + 1) = 5 h (n) + 24 For all n ≥ 0. Let s0 = 9 and let F (k) = 5k + 24 for all k. Example 4: The recursively defined function 1. ƒ (0) = 1 2. ƒ (n + 1) = (n + 1) ƒ(n) for all n ≥ 0 is just the factorial function ƒ(n) = n! Similarly, if a and d are given numbers then the recursively defined function 1. A (0) = a 2. A (n + 1) = A (n) + d for all n ≥ 0 The sequence {A(n)}n∞=0 is usually called the arithmetic progression with initial term and common difference d. If we have used multiplication instead of addition, we would have got geometric progression G(n) =adn and d is known as common ratio. 100 CU IDOL SELF LEARNING MATERIAL (SLM)

The famous Fibonacci sequence is defined recursively: 1. F0 = 1 = F1 2. Fn+1 = Fn + Fn – 1 for all integers n ≥ 1. To find a new Fibonacci sequences add the last two: F2 = F1 + F0 = 2 F3 = F2 + F1 = 3 F4 = F3 + F2 = 5, etc. 5.3.2 Strong Mathematical Induction: • Let P(n)be a statement, for each integer n, which may be either true or false • Then P(n) is true for all positive integers if there is an q ≥ 1 such that 1. P (1), P (2), P (3) …, P(q) are all true 2. When k ≥ q, the assumption that P(i) is true for all integers where 1 ≤ i ≤ k implies that P (k +1) is true [NOTE: The starting value of an integer is different from 1 in the above case] There are three steps involve to use Strong Mathematical Induction Approach. 1. Basis of Induction: Show P (1), P (2), P (3) …, P(q) are all true. 2. Strong Inductive Hypothesis: Assume P(i) is true for all integers I such that 1 ≤ i ≤ k, where k ≥ q. 3. Inductive Step: show that P (k + 1) is true on the basis of the strong inductive hypothesis. Remark: We are allowed to assume P(k) in order to establish P(k+1) is true for above approach. Also, we are supposed to assume not only P(k) but also P (k – 1), P (k – 2) …, P (1) as well to establish (k + 1). Example 5: 1. Prove that the function b(n) = 2(3n) – 5 is the unique function defined by i. b (0) = – 3,b (1) = 1 and ii. b(n) = 4 b (n – 1) – 3 b (n – 2) for n ≥ 2. Proof: First, it is easy to check that b(n) = 2(3n) – 5 does, in fact, satisfy the relation 1 and 2. We will claim that if a(n) is any other function satisfying relation 1 and 2 then a(n) = b(n) for all n. Let P(n): a(n) = b(n) Hence, we will use strong induction method to prove P(n) is true for all non-negative integers n. 101 CU IDOL SELF LEARNING MATERIAL (SLM)

Basis of Induction: Show P (0) = P (1). Since we know that b (0) = - 3,b (1) = 1 and so we are assuming a (0) = – 3,a (1) = 1. Thus, a (0) = b (0) and a (1) = b (1). Strong Inductive Hypothesis: Assume P(i) is true for all 0 ≤ i ≤ k where k ≥ 1 or we can put it in other way like a(i) = b(i) for all integers 0 ≤ i ≤ k where k ≥ 1. Inductive Step: Show that P (k + 1) is true or that a (k + 1) = b (k + 1). By (2), a (k + 1) = 4 a(k) – 3a (k – 1). By Strong Inductive Hypothesis, a (k) = b(k) and a (k – 1) = b (k – 1) since k ≥ 1 and k – 1 > 0. Thus, a (k + 1) = 4 [2 (3k) – 5] – 3[2 (3k – 1 – 1) – 5] = (8) (3k) – (6) (3k – 1) – 5 = (8) (3k) – 2 (3k) – 5 = (6) (3k) – 5 = 2 (3k +1) – 5 = b (k + 1). Hence, proved. 5.4 BASICS OF COUNTING: • Counting is easy, and certainly sometimes it is. But some of the aspects of counting are not simple, especially counting a large number of elements. In this case, we need to use some mathematical skills to find out the answer. • Consider counting the number of elements in a list, where each element has an index beginning with some integer m and ending with some integer n, and m < n. Then there is n - m + 1 elements in the list, from m to n inclusive. For example, if the first index is 0, and the last indexed element is 99, then you have 99 - 0 + 1 = 100 elements. Two elementary principles act as building blocks for all counting problems. 5.4.1 Sum Rule: (The principle of disjunctive Counting) 102 • If a set A is the union of disjoint non-empty subsets X1, X2, …, Xn then CU IDOL SELF LEARNING MATERIAL (SLM)

| A | = | X1 | + | X2 | + … + | Xn |. • The subsets X1, X2… Xn must have no elements in common. • Since A = X1������ X2������…������Xn, each element of A is in exactly one of the subsets Si. • In other words, X1, X2, …, Xn is a partition of A • The sum rule can also be formulated in terms of choices: If an object can be selected from a reservoir in e1 ways and an object can be selected from a separate reservoir in e2 ways, then the selection of one object from either one reservoir or the other can be made in e1 + e2 ways. Example 1: In how many ways can we draw a heart or spade from an ordinary deck of playing cards? A heart or an ace? An ace or a king? A card numbered 2 through 10? A numbered or king? • We know that there are 13 hearts and 13 spades; we may draw a heart or a spade in 13 + 13 = 26 ways. • We may draw a heart or an ace in 13 + 3 = 16 ways since there are only 3 aces that are not hearts. We may draw an ace or a king in 4 + 4 = 8 ways. • There are 9 cards numbered 2 through 10 in each of 4 suits, clubs, diamonds, hearts, or spades, so we may choose a numbered card in 36 ways. Example 2: How many ways can we get a sum of 8 when two indistinguishable dice are rolled? An even sum? • If the dice would been distinguishable, we would obtain sum of 8 by the outcomes (2, 6), (3, 5), (4, 4), (5, 3) and (6, 2) but since dice are similar the outcomes (2, 6) and (6, 2) and, as well, (3, 5) and (5, 3) cannot be differentiated. • So, we obtain the sum of 8 with the roll of two similar dice in only 3 ways • Likewise, we can get an even sum in 1 + 2 + 3 + 3+ 2 + 1 = 12 ways. Example 3: A scholarship is available, and the student to receive this scholarship must be chosen from the Mathematics, Computer Science, or the Engineering Department. How many different choices are there for this student if there are 38 qualified students from the Mathematics Department, 45 qualified students from the Computer Science Department and 27 qualified students from the Engineering Department. • The procedure of choosing a student from the Mathematics Department has 38 possible outcomes, the procedure of choosing a student from the Computer Science Department has 45 possible outcomes, and the procedure of choosing a student from the Engineering Department has 27 possible outcomes. • Therefore, there are (38 + 45 + 27) 110 possible choices for the student to receive the scholarship. 103 CU IDOL SELF LEARNING MATERIAL (SLM)

5.4.2 Product Rule: (The principle of sequential counting) • Suppose that an operation consists of k steps and the first step can be performed in n1 ways; the second step is performed in n2 ways and the kth step can be performed in nk ways. Then the whole operation can be performed in n1⨯ n2⨯… ⨯ nk ways. • If A1, A2, ..., An are non-empty sets, then the number of elements in the Cartesian Product A1 ⨯A2⨯ ...⨯An is the product ∏i=1 |Ai | n • Let us consider two sets A1 = {a1, a2, a3, a4, a5} and A2= {b1, b2, b3}. Thus, we will have following Cartesian product for these two sets as {a1, b1} {a1, b2} {a1, b3} {a2, b1} {a2, b2} {a2, b3} {a3, b1} {a3, b2} {a3, b3} {a4, b1} {a4, b2} {a4, b3} {a5, b1} {a5, b2} {a5, b3} • We have 15 combinations. Also, we can partition the Cartesian Product A1 ⨯A2 as (a1 × A2) ������ (a2 × A2) ������ (a3 × A2) ������ (a4 × A2) ������ (a5 × A2), where (ai×A2) = {(ai, b1), (ai, b2), (ai, b3)} • More generally if a1, a2… an are the n distinct elements of A1 and b1, b2… bm are the m distinct elements of A2, then A1 × A2 = Uni=(1ai × A2)[ U stands for union] • X is an arbitrary element of A1 ×A2 then x = (a, b) where aϵ A1 and b ϵ A2. Thus, a = ai for some i and b = by for some j. Thus, x = (ai, by) ϵ (ai ×A2) and therefore x ϵ Uin=1(ai × A2) • Conversely, if x ϵUi = 1 (ai×A2), then x ϵ (ai×A2) for some i and thus x = (ai, by) whereby is some element of A2. Therefore, x ϵ A1 ×A2. • Next observation is that (ai×A2) and (a×A2) are disjoint if i≠ j since if x ϵ (ai× A2) ∩ (a×A2) then x = (ai, bk) for some k and x= (a, bl) for some l. • But (ai, bk) = (a, bl) implies that ai = aand bk = bl. • Since i ≠ j then ai≠aj.So, we can conclude that A1 × A2 is a disjoint union sets of (ai× A2). • Furthermore, | ai×A2 | = | A2| , there is obviously a one-to-one correspondence between the sets (ai×A2) and A2, namely (ai, bj) → bj. n • Then by the sum rule | A1× A2 | = ∑ i = 1 | ai × A2 | = | A2 | + | A2 | + … + | A2 | = n |A2 | = nm. • We have proved the product rule for two sets Example 4: A man has 10 shirts, 8 pairs of pants and three pairs of shoes. How many different outfits, consisting of one shirt, one pair of pants and one pair of shoes, are possible? 104 CU IDOL SELF LEARNING MATERIAL (SLM)

We have to consider three steps: choose a shirt; choose a pair of pants; and choose a pair of shoes. Choosing a shirt has 10 possible outcomes (as he has ten shirts!), choosing a pair of pants has 8 possible outcomes, and choosing a pair of shoes has 3 possible outcomes. So, the number of different outfits is 10 × 8 × 3 = 240. Example 5: If 2 distinguishable dice are rolled, in how many ways can they fall? If 5 distinguishable dice are rolled, how many possible outcomes are there? How many if 100 distinguishable dice are tossed? • The first die can fall (event E1) in 6 ways and the second can fall (event E2) in 6 ways. Thus, there are 6. 6 = 62 = 36 outcomes when 2 dice are rolled. • Also, the third, fourth and fifth die each have 6 possible outcomes when 2 dice are rolled. Also, third, fourth and fifth die each have 6 possible outcomes so there are 6. 6. 6. 6. 6 = 65 possible outcomes when all 5 dice are tossed. • Likewise, there are 6100 possible outcomes when 100 dice are tossed. Example 6: How many three-digit numbers are there which are even and have no repeated digits? • For a number to be even it must end in 0, 2, 4, 6 or 8. There are two cases to consider. First, suppose that the number ends in 0; then there are 9 possibilities for the first digit and 8 possibilities for the second since no digit can be repeated. Hence there are 9.8 three-digit numbers that end in 0. • Now suppose the number does not end in 0. Then there are 4 choices for the last digit (2,4, 6 or 8); when this digit is specified, then there are only 8 possibilities for the first digit, since the number cannot begin with 0. • Finally, there are 8 choices for the second digit and therefore there are 8.8.4 numbers that do not end in 0. • Accordingly, since these two cases are mutually exclusive, the sum rule gives 9. 8 + 8.8.4 even three-digit numbers with no repeated digits. 5.4.3 Indirect Counting: It stands for counting the complement of a set. We will see the example below for more clarification. Example 7: Suppose that we draw a card from a deck of 52 cards and replace it before the next draw. In how many ways can 10 cards be drawn so that the tenth card is a repetition of a previous draw? • Count the number of ways we can draw 10 cards so that the 10th card is not a repetition. • Choose what the 10th card will be. This can be done in 52 ways. If the first 9 draws are different from this, then each of the 9 draws can be chosen from 51 cards. • Thus, there are 519 ways to draw the first 9 cards different from the 10th card. • There are (519) (52) ways to choose 10 cards with the 10th card different from any of the previous 9 draws. 105 CU IDOL SELF LEARNING MATERIAL (SLM)

• Hence, there are 5210 – (519) (52) ways to draw 10 cards where the 10th is a repetition since there are 5210 ways to draw 10 cards with replacements. ONE-TO-ONE CORRESPONDENCE: • The problem at hand is replaced by another problem where it is observed that there is exactly the same number of objects of the first type as there are of the second type. • It is a set up between the objects of the first type with those of the second. Example 8: Suppose that there are 101 players entered in a single elimination tennis tournament. In such a tournament, any player who loses a match must drop out, and every match end in a victory for some player – there are no ties. In each round of the tournament, the players remaining are matched into as many pairs as possible, but if there is an odd number of players left someone receives a bye (which means entry of that player in next round without playing a match) Enough rounds are played until a single player remains who win the tournament. The problem is how many matches must be played in total? First Approach: • Analyse each round of tournament. The 50 winners and bye will go into the second round and pair into 25 matches and a bye. After this the 25 winners and the bye will go into the third round where there will be exactly 13 matches. The fourth round will have six matches and a bye; the fifth round, 3 matches and a bye; the sixth, 2 matches; the seventh will have 1 match and the winner of the seventh round wins the entire tournament. In total, there must be 50 + 25 +13 + 6 + 2 +1 = 100 matches. Second Approach: • There is one-to-one correspondence between the number of matches and the number of losers. • Each match has only one and one loser • So, Total number of matches = total number of losers • At the start there are 101 players and at the end only one as a winner so this implies there are 100 players who are losers. For 100 losers there are 100 matches need to be conducted to determine a winner. APPLICATIONS TO COMPUTER SCIENCE: • A 2- valued Boolean function of n variables is defined by the assignment of a value of either 0 or 1 to each of the 2n n digit binary numbers. How many Boolean functions of n variables are there? • Since there are 2 ways to assign a value to each of the 2n binary n tuples, so by the rule of product 22 different Boolean functions of n variables. • The following truth table of a 2-valued Boolean function of four variables: 106 CU IDOL SELF LEARNING MATERIAL (SLM)

Four Digit Binary Number Value 0000 0 0001 1 0010 1 0011 0 0100 1 0101 0 0110 0 0111 0 1000 1 1001 0 1010 0 1011 0 1100 0 1101 0 1110 0 1111 0 • A self-dual 2 valued Boolean function is one which will remain unchanged after all the 0’sand 1’s in the truth table is interchanged. • How many self-dual 2-valued Boolean functions of n variables are there? • Partition the set of 2n binary n tuples into 2n – 1 block, each block containing an n tuple and its 1’s complement. • In constructing a self-dual function, assigning a value to either member of a block fixes the value that must be given to the other member. 107 CU IDOL SELF LEARNING MATERIAL (SLM)

• So independent value assignments may be made for only 2n – 1 of the 2n tuples. Thus, there are 22 different self-dual Boolean fun–n1ctions of n variables. Factorials: For each positive integer we define n! = n. (n – 1) (n – 2) … 3. 2. 1 = the product of all integers from 1 to n. Also 0! = 1 and 1! = 1 Thus, 4! = 4.3.2.1 7! = 7.6.5.4.3.2.1 3! = 3.2.1 We read n! as n factorial. 5.5 SUMMARY Combinatorics has many applications in other areas of mathematics, including graph theory, coding and cryptography, and probability. Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. The technique involves two steps to prove a statement, as stated below − Step 1(Base step) − It proves that a statement is true for the initial value. Step 2(Inductive step) − It proves that if the statement is true for the nth iteration (or number n), then it is also true for (n+1) th iteration (or number n+1). Recursion Theorem: The first condition of the Recursion Theorem is called the initial condition and Second condition is called the recurrence relation or generating rule. Both the parts are necessary for conclusion of the theorem Strong Mathematical Induction: Strong Induction is another form of mathematical induction. Through this induction technique, we can prove that a propositional function, P(n)P(n) is true for all positive integers, nn, using the following steps − • Step 1(Base step) − It proves that the initial proposition P (1)P(1) true. • Step 2(Inductive step) − It proves that the conditional statement [P (1) ������P (2) ������P (3) ������⋯������P(k)] →P(k+1) is true for positive integers k 108 CU IDOL SELF LEARNING MATERIAL (SLM)

Direct Counting: The Sum Rule: If there are n(A) ways to do A and, distinct from them, n(B) ways to do B, then the number of ways to do A or B is n(A) + n(B). The Product Rule: If there are n(A) ways to do A and n(B) ways to do B, then the number of ways to do A and B is n(A) × n(B) Indirect Counting: It stands for counting the complement of a set. 5.6 KEYWORDS • Mathematical Induction: is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. • Strong induction is a type of proof closely related to simple induction. • Factorial: the product of an integer and all the integers below it • One-to-one correspondence is an early learning math skill that involves the act of counting each object in a set once, and only once with one touch per object. • Sequential Counting: is a Procedure for Estimating the Total Number of. Randomly Distributed Individuals. 5.7 LEARNING ACTIVITY 1. Using the principle of mathematical induction, prove that 1² + 2² + 3² + ..... + n² = (1/6) {n (n + 1) (2n + 1} for all n ∈ N. 2. Using the principle of mathematical induction, prove that 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ..... + n (n + 1) = (1/3) {n (n + 1) (n + 2)}. 5.8 UNIT END QUESTIONS 109 A. Descriptive Questions 1. What is Mathematical Induction? 2. Explain Strong Mathematical Induction with example? CU IDOL SELF LEARNING MATERIAL (SLM)

3. What is Recursion Theorem? State and prove. 4. Write a note on Indirect Counting 5. Explain counting application B. Multiple Choice Questions 1. In the principle of mathematical induction, which of the following steps is mandatory? a) Induction hypothesis b) inductive reference c) induction set assumption d) minimal set representation 2. For m = 1, 2, …, 4m+2 is a multiple of a) 3 b) 5 c) 6 d) 2 3. For every natural number k, which of the following is true? a) (mn)k = monk b) m*k = n + 1 c) (m+n) k = k + 1 d) mkn = mnk 4. For any positive integer m is divisible by 4. a) 5m2 + 2 b) 3m + 1 c) m2 + 3 d) m3 + 3m 5. What is the induction hypothesis assumption for the inequality m!> 2m where m>=4? a) for m=k, k+1!>2k holds b) for m=k, k!>2k holds 110 CU IDOL SELF LEARNING MATERIAL (SLM)

c) for m=k, k!>3k holds d) for m=k, k!>2k+1 holds 6. or any integer m>=3, the series 2+4+6+…+(4m) can be equivalent to a) m2+3 b) m+1 c) mm d) 3m2+4 7. For any positive integer m is divisible by 4. a) 5m2 + 2 b) 3m + 1 c) m2 + 3 d) m3 + 3m 8. According to principle of mathematical induction, if P(k+1) = m(k+1) + 5 is true then must be true. a) P(k) = 3m(k) b) P(k) = m(k) + 5 c) P(k) = m(k+2) + 5 d) P(k) = m(k) 9. Which of the following is the base case for 4n+1 > (n+1)2 where n = 2? a) 64 > 9 b) 16 > 2 c) 27 < 91 d) 54 > 8 10. What is the induction hypothesis assumption for the inequality m!> 2m where m>=4? 111 a) for m=k, k+1!>2k holds b) for m=k, k!>2k holds c) for m=k, k!>3k holds d) for m=k, k!>2k+1 holds Answers: CU IDOL SELF LEARNING MATERIAL (SLM)

1 – a; 2 – d;3 – a; 4 – d; 5 – b; 6 – a; 7 – d; 8 – b; 9 – a; 10 – b 5.9 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. • C Liu, D. Mohapatra, Elements of Discrete Mathematics: A Computer Oriented Approach | 4th Edition, McGraw Hill Education • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford • V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc • 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. • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 112 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 6- COMBINATORICS 2 Structure 6.0. Learning Objectives 6.1. Introduction 6.2. Combination and Permutation 6.3. The principle of Inclusion-exclusion. 6.4. Summary 6.5. Keywords 6.6. Learning Activity 6.7. Unit End Questions 6.8. References 6.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • Explain the Combination and Permutation • Comprehend the principle of Inclusion-exclusion. 6.1 INTRODUCTION Combinatorics is a branch of mathematics which is about counting – and we will discover many exciting examples of “things” you can count. First combinatorial problems have been studied by ancient Indian, Arabian and Greek mathematicians. Interest in the subject increased during the 19th and 20th century, together with the development of graph theory and problems like the four-colour theorem. Some of the leading mathematicians include Blaise Pascal (1623 – 1662), Jacob Bernoulli (1654 – 1705) and Leonhard Euler (1707 – 1783). Let us consider a salad, that is a mix of celeriac, walnuts and lettuce. We are not concerned about the order of ingredients but similarly if we have a combination to our locker that is 4-5-6 then the order is extremely important. If the order doesn't matter then we have a combination, if the order do matter then we have a permutation. One could say that a permutation is an ordered combination. The solution to many statistical experiments involves being able to count the number of points in a sample space. Counting points can be hard, tedious, or both. Sometimes, we want to count all of the possible ways that a single set of objects can be selected - without regard to the order in which they 113 CU IDOL SELF LEARNING MATERIAL (SLM)

are selected. Often, we want to count all of the possible ways that a single set of objects can be arranged. For example, consider the letters X, Y, and Z. These letters can be arranged a number of different ways (XYZ, XZY, YXZ, etc.) Each of these arrangements is a permutation. The principle of inclusion and exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties while guaranteeing that elements satisfying more than one property are not counted twice. An underlying idea behind PIE is that summing the number of elements that satisfy at least one of two categories and subtracting the overlap prevents double counting. For instance, the number of people that have at least one cat or at least one dog can be found by taking the number of people who own a cat, adding the number of people that have a dog, then subtracting the number of people who have both. PIE is particularly useful in combinatorics and probability problem solving when it is necessary to devise a counting method that ensures an object is not counted twice. 6.2 COMBINATION AND PERMUTATION • We use word combination in so many ways in our day to day lives. • Example: • \"My fruit salad is a combination of apples, grapes and bananas\" We don't care what order the fruits are in, they could also be \"bananas, grapes and apples\" or \"grapes, apples and bananas\", it’s the same fruit salad. • \"The combination to the locker was 472\". Now we do care about the order. \"724\" would not work, nor would \"247\". It has to be exactly 4-7-2. • We use more precise language in mathematics. • If the order doesn't matter, it is a Combination • If the order does matter it is a Permutation Definition: A combination of n objects taken r at a time is an unordered selection of r of the objects. Definition: A permutation of n objects taken r at a time (also called an r- permutation of n objects) is an ordered selection or arrangement of r of the objects. Or simply A Permutation is an ordered Combination. We will see some examples to get more understanding on the above topics. • Example: Suppose that the 4 objects from which the selections are supposed to be made: a, a, b, c. Then the 3 combinations of these 4 objects are: aab, aac, abc. 114 CU IDOL SELF LEARNING MATERIAL (SLM)

The 3 – permutation: aab, aba, baa, aac, aca, caa, abc, acb, bac, bca, cab, cba. So, in the above example, there is a need of rule that allows a given object to be repeated upto certain specified number of times. • Example like {2.a, 3. B, 4.c} indicates that the selection is constrained by the condition that a can be selected at the most two times, b can be selected at the most three times and c can be chosen upto four times. • The number 2, 3 and 4 in the above example is called repetition number. • The 3-combinations of {∞. A, 5.b, ∞.c}—if we are considering selections where each object has ∞ as its repetition number then we designate such selections as selection with unlimited repetition. If we select r objects in this case will be called r-combination with unlimited repetitions and r ordered arrangement of these r objects will be known as r- permutation with unlimited repetitions. • Example: Suppose the 2 permutations of {∞. a, ∞. b, ∞.c, ∞. d} 2- Combination with Unlimited 2- Permutation with unlimited Repetitions Repetitions aa aa 115 ab ab, ba ac ac, ca ad ad, da bb bb bc bc, cb bd bd, db cc Cc cd cd, dc s [-p0 dd Dd CU IDOL SELF LEARNING MATERIAL (SLM)

Total Number =10 Total Number =16 Example 1: The 3- combinations of {∞. a, ∞. b, 2.c, 2.d} where b can be chosen only an even number of times are the 3-combinations of a, b, c, d where a can be chosen upto 3 times, bcan be chosen either 0 or 2 times, and c and d can be chosen at most 2 times. The 3-combination subject to these constraintsare: aaa, aac, aad, acc, add, bba, bbc, bbd, acd • If the repetitions numbers are all 1, then the selection of r objects are called r-combinations without repetitions and arrangements of the objects are r-permutation without repetitions. Also, r- combinations without repetitions are just subsets of the n element containing exactly r elements. • Example 2: Suppose selections are to be made from the four objects a, b, c, d. 2- Combinations without 2- permutations without repetitions repetitions ab ab, ba ac ac, ca ad ad, da bc bc. cb bd bd, db cd cd, dc Total number = 6 Total number = 12 ENUMERATION OF COMBINATION AND PERMUTATIONS: 116 Let P (n, r) denote the number of r – permutations of n elements without repetitions. THEOREM: CU IDOL SELF LEARNING MATERIAL (SLM)

P (n, r) = n (n – 1) … (n – r + 1) = n! (n – r)! PROOF: Since there are n distinct objects, the first position of an r – permutation may be filled in n ways. The second position can be filled in n – 1 way since no repetitions are allowed and there is n – 1 way since repetitions are not allowed so we have to choose from n – 1 left over objects. The third can be filled in n – 2 ways and so on till rth position is filled in n – r + 1 ways. Now apply the product rule and we can conclude that P (n, r) = n (n – 1) (n – 2) … (n – r + 1). Referring to the definition of the factorials, it follows that P (n, r) = n! (n – r)! When we consider the permutation of nobjects, we mean the case r = n, we assume that all the objects are to be arranged. COROLLARY: There are n! permutations of n distinct objects. Example 1: There are P (10,4) = 5040 4-digit numbers that contain no repeated digits since each such number is just an arrangement of four of the digits 0,1,2,3 …, 9. There are P (26, 3) 3-letter words formed from the English alphabet with no repeated letters. Thus, there are P (26, 3) (10, 4) license plates are formed by 3 distinct letters followed by 4 distinct digits. Example 2: In how many ways can the letters of the English alphabet be arranged so that there are exactly 5 letters a and b? There are P (24, 5) ways to arrange the 5 letters between a and b, 2 ways to place a and b, and then 20! ways to arrange any 7-letter word treated as one unit along with the remaining 19 letters. The total is P (24, 5) (20!) (2) Example 3: How many 6-digits numbers without repetition of digits are there such that the digits are all non-zero and 1 and 2 do not appear consecutively in either order? In the table below we will separate these 6-permutations into 4 disjoint classes and count the number of permutations in each class 117 CU IDOL SELF LEARNING MATERIAL (SLM)

Class Number of Permutation in the class Neither 1 nor 2 appears as a digit 7! 1, but not 2 appears as a digit 2, but not 1, appears 6 P (7, 5) Both 1 and 2 appears 6 P (7, 5) (2)(7)(4) P (6, 3) + (4)(7)(6)(3) P (5, 2) Total 7! + (2)(6) P (7, 5) + 56 P (6, 3) + (504) P (5, 2) • Let see in brief how to count the elements in class(iv) • The Hundred thousand digit is 1 and so the ten thousand digit is not 2. The second digit can be chosen in 7 ways. • Choose the position for 2 in 4 ways; then fill the other 3 positions P (6, 3) ways. Hence, there are (7) 4 (6, 3) numbers in this category. • Now the unit digit is 1 so ten digits is not 2. Similarly, there are numbers in this category. • The integer 1 appears in a position different from the hundred thousand digit and the unit’s digit. Hence, 2 cannot appear immediately to the left or right of 1. Since 1 can be anyone of the digits from the tens digit up to the ten-thousand-digit, 1 can be placed in 4 ways. • The digit immediately to the left of 1 can be filled in 7 ways, while the digit immediately to the right of 1 can be filled in 6 ways. • The integer 2 can be placed in any of the remaining position in 3 ways and then the other 2 digits are a 2-permutation of the remaining 5 integers. Hence there are • (4)(7)(6)(3) P (5, 2). • Thus, there are • (2)(6) P (7, 5) + 56 P (6, 3) + (504) P (5, 2) numbers in class (iv). 118 CU IDOL SELF LEARNING MATERIAL (SLM)

• Now apply the sum rule, then we have • 7! + (2)(6) P (7, 5) + 56 P (6, 3) + (504) P (5, 2) elements in four classes. Such type of permutation which we have considered so far is known as linear permutations for the objects are being arranged in a line. Example 4: In a library, there are 4 books on fairy tales, 5 books are novels and 3 books are on plays. In how many ways can you arrange these so that books on the fairy tales are together in one place. The novels are together and plays are also together. The requirement is that these books should be in a specific order i.e., books on fairy tales, before novels, before plays. Solution: There are 4 books on fairy tales and they have to be put together. They can be arranged in 4! ways. Similarly, there are 5 novels. They can be arranged in 5! ways. And there are 3 books on plays. They can be arranged in 3! ways. So, by the counting principle all of them together can be arranged in 4! × 5! × 3! ways = 17280 ways. Example 5: In the above example what is the number of permutations if the books are not to be kept in order? Solution: Whenever you are asked to keep a particular class of objects together, a convenient trick is to sort of glue them together in your head and treat them as one object. First, we consider the books on fairy tales, novels and plays as single objects. These three objects i.e., the one group of fairy tale books, the one group of novels and the one group of plays can be arranged in 3! ways = 6 ways. Let us fix one of these 6 arrangements. This may give us a specific order, say, novels → fairy tales → plays. Given this order, the books on the same subject can be arranged as follows. In other words, now we have to count the internal permutations. The 4 books on fairy tales can be arranged among themselves in 4! = 24 ways. The 5 novels can be arranged in 5! = 120 ways. The 3 plays can be arranged in 3! = 6 ways. For a given order, the books can be arranged in 24×120×6 = 17280 ways. Therefore, for all the 6 possible orders the books can be arranged in 6×17280 = 103680 ways. 119 CU IDOL SELF LEARNING MATERIAL (SLM)

THEOREM: There are (n – 1)! Permutation of n distinct objects in a circle. • Let C (n, r)- denote the number of r-combinations of n distinct objects where 1 is the repetition number for each element. • A is a set with n elements. • So, C (n, r) is the number of r-combinations of n elements without repetitions. • C (n, r) is also known as binomial co-efficient because of its role in the expansion of (x + y) n • Instead of C (n, r) we can use the notation (n) THEOREM: [Enumerating r combinations without repetitions] Any r permutation of n objects can be obtained by first choosing the relements which can be done in C(n, r) ways. Then arrange the r elements in all possible orders which can be done in r! ways. Thus, we get P (n, r) = r! C (n, r) Therefore, C (n, r) = P (n, r) = n! r!r! (n – r)! Example 6: a. How many 5-card hands consist only of hearts? Solution: As there are 13 hearts cards to choose from, each such hand is a 5 combination of 13 objects. So we have total as C (13, 5) = 13! = 13 .12 .11 .10 . 9 [Cancelling 12 with 4.3 and 10 with 5!8! 5 .4 .3 .2 .1 5.2] = 13 .11. 9 = 1287. b. How many 5- card hands have 2 cards of one suit and 3 cards of a different suit? Solution: There are 2C (13, 2) C (13, 3) ways to choose 2 from one of the suits and 3 from the other. 120 CU IDOL SELF LEARNING MATERIAL (SLM)

We can choose the 2 suits in C (4, 2) ways. Thus, there are 2C (13, 2) C (13, 3) C (4, 2) such as 5- card hands. As we are aware that two of a kind means 2 aces, 2 kings, 2 queens etc. Similarly, 3 tens are called three of a kind. Thus, there are 13 “kinds” in a deck of 52 cards. c. How many 5-card hands contain exactly 2 of one kind and 3 of another kind? Solution: Choose the first kind 13 ways, choose 2 of the first kind C (4, 2) ways. Choose the second 12 ways and choose 3 of the second kind in C (4, 3) ways. Hence, there are (13) C (4, 2) (12) C (4, 3) 5-card hands with 2 of one kind and 3 of the other kind. Example 7: There are 21 consonants and 5 vowels in the English Alphabet. Consider only 8-letter words with 3 different vowels and 5 different consonants. a. How many such words can be formed? Solution: Choose the vowels, choose the consonants and arrange the 8 letters C (5, 3) C (21, 5) 8! b. How many such words contain the letter a? C (4, 2) C (21, 5)8! c. How many contain the letters a and b? C (4, 2) C (20, 4)8! d. How many contain the letters a, b and c? C (4, 2) C (19, 3)8! e. How many begin with a and end with b? C (4, 2) C (20, 4)6! ENUMERATING COMBINATIONS AND PERMUTATIONS WITH REPETITIONS: Let U (n, r) – denote the number of r-permutations of n objects with unlimited repetitions and let V (n, r) - denote the number of r-combinations of n objects with unlimited repetitions. Thus, if x1, x2, … ,xn are n objects we are counting r-combinations and r-permutations of {∞ . x1, ∞ .x2 , …,∞ .xn } THEOREM1: Enumerating r-permutations with unlimited repetitions U (n, r) = nr PROOF: Each of the r position can be filled in n ways and so by the product rule, U(n, r) = nr Example 8: How many 10-digit binary numbers are there with exactly six 1’s? Solution: We can specify a binary number by choosing the subset of 6 positions where the 1’s go (or the subset of 4 positions for the 0’s). Thus, there are C(10, 6) = C(10, 4) = 210 such binary numbers. 121 CU IDOL SELF LEARNING MATERIAL (SLM)

• To derive the formula for enumerating combinations with unlimited repetitions, we will reformulate the problem in several different ways Let the distinct objects be a1, a2, …, an so that selections are made from { ∞ . a1, ∞ . a2, …,∞.an }. Any r- combination will be of the form { x1 . a1, x2. a2, …, xn.an} where x1, x2, …, xn are the repetition numbers, each xi is non-negative, and x1+ x2 + … + xn =r. Conversely, we can say that any sequence of non-negative integersx1, x2, …, xn where x1+ x2 + … + xn =r corresponds to an r- combination {x1. a1, x2. a2, …, xn .an} First Observation: The number of r- combinations of {∞. a1, ∞.a2, …, ∞.an} equals the number of solutions of x1+ x2 + … + xn =r inn on-negative integers. Second Observation: The number of non-negative integral solutions of x1+ x2 + … + xn =r is equal to the number of ways of placing r distinguishable balls in n numbered boxes. Third Observation: The number of ways of placing r indistinguishable balls in n numbered boxes is equal to the number of binary numbers with (n – 1) 1’s and r 0’s. If there are x1 balls in box number 1, x2 balls in box number 2, …, xn balls in box number n, then in a corresponding binary number let there be x1 0’s to the left of the first 1, x2 0’s between the first and the second 1 and finally xn 0’s to the right of the last 1. (Note: Two consecutive 1 means there were no balls in the box). Suppose r = 7 and n =10in the above, that is we are interested in 7-combinations of {∞. a1, ∞. a2, …, ∞.an}. To the7- combination a1, a2, a3, a4, a5, a6, a7, a8 we associate the solution (3,0,0,2,0,0,2,0,0) of x1+ x2 + … + x10 =7. Then to the solution (3,0,0,2,0,0,2,0,0) we associate the distribution of 3 balls in box 1, 0 balls in boxes 2, 3, 5, 6, 7, 9 and 10, 2 balls in box 4, and 2 balls in box 8. To these distribution of balls associates the binary number 0001110011110011. Conversely, to any such binary number with (n – 1) 1’s and r 0’s we associate the distribution of r balls into n boxes by reversing the above process. We will consider reverse of the above example. The binary number 11000110101111001 signifies that there are no balls in boxes 1, 2, 4,7, 8 or 10, 3 balls in box 3, 2 balls in box 9 and 1 ball each in boxes 5 and 6. To this distribution of balls is associated with the solution (0,0,3,0,1,1,0,0,2,0) of x1+ x2 + … + x10 =7. So, 7-combination {3. a3, 1. a5, 1. a6, 2. a9}. 122 CU IDOL SELF LEARNING MATERIAL (SLM)

Fourth Observation: The number of binary numbers with n – 1 1’s and r 0’s is C (n – 1 +r, r). THEOREM: Enumerating r-combinations with unlimited repetitions V (n, r) = the number of r-combinations of n distinct objects with unlimited repetitions = the number of non-negative integral solutions to x1+ x2 + … + xn =r = the number of ways of distributing r similar balls into n number of boxes = the number of binary numbers with n – 1 one’s and r zeros. = C (n – 1 +r, r) = C (n – 1 + r, n – 1) = (n + r – 1)! /[r! (n – 1)!] Remark: The number of r- combinations of {∞. a1, ∞. a2, …, ∞.a} is same as the number of r- combinations of {r. a1, r. a2, …, r. an} Example 9: a. The number of 4-combination of {∞. a1, ∞. a2, ∞. a3, ∞. a4, ∞. a5} is C (5 – 1 + 4, 4) = C (8, 4) = 70 b. The number of 3-combinations of 5-objects with unlimited repetitions is C (5 – 1+ 3, 3) = C (7, 3) = 35 c. The number of non-negative integral solutions to x1+ x2 + x3 + x4+ x5 = 50 is C (5 – 1 + 50, 50) = C (54, 50) = 54! / 4!50! = 27. 53. 17. 13 = 316,251. d. The number of ways of placing 10 similar balls in 6 numbered boxes is C (6 – 1 + 10, 10) = C (15, 10) = 3,003. e. The number of binary numbers with ten 1’sand five 0’s is C (10 + 5, 5) = C (15, 5) = 3,003. THEOREM: The number of integral solutions of x1+ x2 + … + xn =r where each xi> 0 = the number of ways of distributing r similar balls into n numbered boxes with at least one ball in each box = C (n – 1 + (r – n), r – n) = C (r – 1, r – n) = C (r – 1, r – n) 123 CU IDOL SELF LEARNING MATERIAL (SLM)

Likewise, suppose that r1, r2, …,rn are integers. Then the number of integral solutions of x1+ x2 + … + xn =r where x1 ≥ r1, x2 ≥ r2,…, and xn ≥ rn = the number of ways of distributing r similar balls into n numbered boxes where there is at least r1 in the first box, at least r2 in the second box, …, and at least rn in the nth box = C (n – 1 + r – r1 – r2 – … – rn, r – r1 – r2 – …– rn) = C (n – 1 + r – r1 – r2– …– rn, n – 1) Example 10: Enumerate the number of non-negative integral solutions to the inequality x1+ x2 + x3 + x4+ x5 ≤ 19. Solution: • Let x1+ x2 + x3 + x4+ x5 = m where m can be any integer from 0 to 19. • There are C (5 – 1 + 0, 4) + C (5 – 1 + 1, 4) + … + C (5 – 1 + 19, 4) such solutions. [With reference to theorem 1] • We have 19 similar balls and we are counting the number of ways of distributing either 0 or 1, or 2, …, or 19 of these balls into the 5 boxes. • Alternatively, if m is some integer between 0 and 19, then for every distribution of m ball into 5 boxes, one could distribute the remaining 19 – m balls into a sixth box. • Hence the number of non- negative integral solutions of x1+ x2 + x3 + x4+ x5 ≤ 19 is the same as the number of non-negative integral solutions of y1+ y2 + y3 + y4 + y5 + y6 = 19. • With reference to theorem 1 there are C (6 – 1 + 19, 5) = C (24, 5) = C (24, 19) such solutions. • We conclude that 19 19 C (24, 5) = ∑ C (4 + m, m) = ∑ C (m + 4, 4) m=0 m=0 6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION: In some cases, the sets are not disjoint, so to count the number of elements in the union of such sets we apply the principle of inclusion-exclusion which is the refine version of the sum rule that is useful in counting the number of elements in the union of disjoint sets. 124 CU IDOL SELF LEARNING MATERIAL (SLM)

First Statement: If A and B are subsets of some universe set U, then |A ������ B| = |A| + |B| − |A ∩ B|..................................................................(1) The Venn diagram related to above statement is as follow: ������ ∩ ���̅ ��� ������ ∩ ������̅ Fig 6.1: Venn Diagram representing two sets A and B From the above Venn Diagram, it is clear that while counting the elements in the union of set A and B, the elements which are common to both the sets are counted twice. Also, it is clear thatA ������ B is the union of the three disjoint sets viz. A ∩ B, A ∩ B̅ and A̅ ∩ B. By the sum rule, we can write |A ������ B| = |A ∩ B| + |A ∩ B̅| + |A̅ ∩ B| ..........................................................(2) Also, we can write A = (A ∩ B̅) ������ (A ∩ B)and B = (A̅ ∩ B) ������ (A ∩ B), Now |A| = |A ∩ B| + |A ∩ B̅|&|B| = |A ∩ B| + |A̅ ∩ B| Adding |A|&|B|, we get |A| + |B| = |A ∩ B| + |A ∩ B̅| + |A ∩ B| + |A̅ ∩ B| ....................................... (3) 125 CU IDOL SELF LEARNING MATERIAL (SLM)

Using equation (2) we can modify equation (3) |A| + |B| = |A ������ B| + |A ∩ B| Therefore, |A ������ B| = |A| + |B| − |A ∩ B| [Note: If A ∩ B = ∅, then the above principle is just the sum rule.] We can write the above principle in term of statement as the sets are commonly defined in terms of properties: ‘The number of elements with either of the properties A or B equals the number of elements with property A plus the number of elements with property B minus the number of elements that satisfy both properties A and B.’ Example 1: Suppose that 200 faculty members can speak French and 50 can speak Russian, while only 20 can speak both French and Russian. How many faculty members can speak either French or Russian? Solution: Let F be the set of faculty members who speak French, R be the set of faculty members who speak Russian. It is given that |F| = 200 ,|R| = 50 and |F ∩ R| = 20 We are interested to find out |F ������ R|. Using the principle of inclusion-exclusion we can write |F ������ R| = |F| + |R| − |F ∩ R| |F ������ R| = 200 + 50 − 20 |F ������ R| = 230 126 CU IDOL SELF LEARNING MATERIAL (SLM)

Theorem: We can write the principle of Inclusion-Exclusion for three sets. Consider A, B and C are the three finite sets, then |A ������ B ������ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| Example 2: In a survey of student at Florida State University the following information was obtained: 260 were taking a statistics course, 208 were taking a mathematics course, 160 were taking a computer programming course, 76 were taking statistics and mathematics, 48 were taking statistics and computer programming, 62 were taking mathematics and computer programming, 30 were taking all three kinds of courses, and 150 were taking none of the 3 courses. a. How many students were surveyed? b. How many students were taking a statistic and a mathematics course but not a computer programming course? c. How many were taking a statistic and a computer course but not a mathematics course? d. How many were taking a computer programming and a mathematics course but not a statistics course? e. How many were taking a mathematics course but not taking a statistics course or a computer programming course? f. How many were taking a statistics course but not taking a course in mathematics or in computer programming? g. How many were taking a computer programming course but not taking a course in mathematics or in statistics? Solution: Let S = be the set of the students taking statistics; M = be the set of the students taking mathematics; C= be the set of the students taking computer programming. Given:|S| = 260, |M| = 208, |C| = 160, 127 |S ∩ M| = 76, |S ∩ C| = 48, |M ∩ C| = 62 CU IDOL SELF LEARNING MATERIAL (SLM)

|S ∩ M ∩ C| = 30and̅|S∩M̅∩̅C̅| = 150 Let us draw the Venn diagram as well that will help us in the analysis. Fig 6.2: Venn Diagram for Example 2 representing survey of student at Florida State University a. The total numbers of student surveyed: |U| = |S ������ M ������ C| + |̅���S̅M������̅ ̅C̅|��� = |S| + |M| + |C| − |S ∩ M| − |S ∩ C| − |M ∩ C| + |S ∩ M ∩ C| + |̅S̅���̅M���̅���C̅ ̅|��� = 260 + 208 + 160 − 76 − 48 − 62 + 30 + 150 = 622 |U| = 622. b. Here we are interested to find |S ∩ M ∩ C̅| = |S ∩ M − S ∩ M ∩ C| = |S ∩ M| − |S ∩ M ∩ C| = 76 − 30 = 46 |S ∩ M ∩ C̅| = 46 128 CU IDOL SELF LEARNING MATERIAL (SLM)

c. |S ∩ C ∩ M̅ | = |S ∩ C| − |S ∩ M ∩ C| = 48 − 30 = 18 d. |M ∩ C ∩ S̅| = |M ∩ C| − |S ∩ M ∩ C| = 62 − 30 = 32 e. |M ∩ S̅ ∩ C̅| = |M| − |S ∩ M ∩ C̅| − |S̅ ∩ M ∩ C| − |S ∩ M ∩ C| = 208 − 46 − 32 − 30 = 100 f. |S ∩ M̅ ∩ C̅| = |S| − |S ∩ M ∩ C̅| − |S ∩ M̅ ∩ C| − |S ∩ M ∩ C| = 260 − 46 − 18 − 30 = 166 g. |S̅ ∩ M̅ ∩ C| = |C| − |S ∩ M̅ ∩ C| − |S̅ ∩ M ∩ C| − |S ∩ M ∩ C| = 160 − 18 − 32 − 30 = 80 General Statement of the principle of inclusion-exclusion: If Aiare finite subsets of a universal set U, then n |A1 ������ A2 ������ … An| = ∑|Ai| − ∑|Ai ∩ Aj| + ∑|Ai ∩ Aj ∩ Ak| + ⋯ + (−1)|A1 ∩ A2 … ∩ An| i=1 i,j i,j,k Where the second summation is taken over all 2-combinations {i, j} of the integers {1, 2… n}, the third summation is taken over all 3-combinations {i, j, k} of {1, 2…n} and so on. Corollary:|̅A̅1∩ ̅A2̅ ∩ … ∩ ̅A̅n| = |U| − |A1 ������ A2 ������ … ������ An| n = |U| − ∑|Ai| + ∑|Ai ∩ Aj| − ∑|Ai ∩ Aj ∩ Ak| + ⋯ + (−1)|A1 ∩ A2 … ∩ An| i=1 i,j i,j,k Example: Count the number of integral solutions to the following equation stated below. a1 + a2 + a3 = 20 where 2 ≤ a1 ≤ 5; 4 ≤ a2 ≤ 7 and − 2 ≤ a3 ≤ 9 … . (1) Solution: Let U be the universal set of solutions (a1, a2, a3) where 2 ≤ a1; 4 ≤ a2 and − 2 ≤ a3 So, |U| = C(20 − 2 − 4 + 2 + 3 − 1, 3 − 1) = C(18, 2) 129 CU IDOL SELF LEARNING MATERIAL (SLM)

Let A1 = {(a1, a2, a3) ∈ U|a1 ≥ 6} A2 = {(a1, a2, a3) ∈ U|a2 ≥ 8} A3 = {(a1, a2, a3) ∈ U|a3 ≥ 10} 123 Here we are interested to count the number of elements in ̅1A∩ ̅A2∩ A̅ ̅3= ̅A(���̅ ̅���A���)���. Now using the principle of inclusion-exclusion, A̅(̅���̅A���̅���A)��� = |U| − |A ������ A ������ A | 123 123 = |U| − {|A1| + |A2| + |A3| − |A1 ∩ A2| − |A1 ∩ A3| − |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|} Now A1 is the set of solution of the equation (1) where 6 ≤ a1; 4 ≤ a2 and − 2 ≤ a3 Thus, |A1| = C(20 − 6 − 4 + 2 + 3 − 1, 3 − 1) = C(14, 2) Similarly, A2 is the set of solution of the equation (1) where 2 ≤ a1; 8 ≤ a2 and − 2 ≤ a3 |A2| = C(20 − 2 − 8 + 2 + 3 − 1, 3 − 1) = C(14, 2) Likewise, A3 is the set of solution of the equation (1) where 2 ≤ a1; 4 ≤ a2 and 10 ≤ a3 |A3| = C(20 − 2 − 4 − 10 + 3 − 1, 3 − 1) = C(6, 2) Now, A1 ∩ A2 is the set of solutions where 6 ≤ a1; 8 ≤ a2 and − 2 ≤ a3 Thus, |A1 ∩ A2| = C(20 − 6 − 8 + 2 + 3 − 1, 3 − 1) = C(10, 2) Similarly, |A1 ∩ A3| = C(20 − 6 − 4 − 10 + 3 − 1, 3 − 1) = C(2, 2) |A2 ∩ A3| = C(20 − 2 − 8 − 10 + 3 − 1, 3 − 1) = C(2, 2) Moreover |A1 ∩ A2 ∩ A3| = 0 since 20 does not exceed 6+8+10. Therefore, ̅A(̅���̅A���̅���A)��� = C(18,2) − 2C(14,2) − C(6,2) + C(10,2) + 2C(2,2). 123 6.4 SUMMARY There are numerous applications related to permutation and combinations. We have learned about the concept and important theorems of permutation and combination. We have studied the Exclusion and Inclusion Principle. • A combination of n objects taken r at a time is an unordered selection of r of the objects. 130 CU IDOL SELF LEARNING MATERIAL (SLM)

The number of combinations of n objects taken r at a time is denoted by nCr. • A permutation of n objects taken r at a time (also called an r- permutation of n objects) is an ordered selection or arrangement of r of the objects. Or simply A Permutation is an ordered Combination. The number of permutations of n objects taken r at a time is denoted by nPr. • If we select r objects in this case will be called r-combination with unlimited repetitions and r ordered arrangement of these r objects will be known as r- permutation with unlimited repetitions. • Linear permutations for the objects are being arranged in a line. • Circular Permutation - Permutation of n distinct objects in a circle. • Enumerating r combinations without repetitions- Any r permutation of n objects can be obtained by first choosing the r elements which can be done in C (n, r) ways. • The principle of inclusion and exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties while guaranteeing that elements satisfying more than one property are not counted twice • General Statement of the principle of inclusion-exclusion: If Ai are finite subsets of a universal set U, then • |A1 ������ A2 ������ … An| = ∑n |Ai| − ∑ |Ai ∩ Aj| + ∑ |Ai ∩ Aj ∩ Ak| + ⋯ + (−1)|A1 ∩ A2 … ∩ i=1 i,j i,j,k An| 6.5 KEYWORDS • Combination: A combination of n objects taken r at a time is an unordered selection of r of the objects. • Permutation: A permutation of n objects taken r at a time (also called an r- permutation of n objects) is an ordered selection or arrangement of r of the objects. Or simply A Permutation is an ordered Combination. • Enumeration: An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. • Repetition - The act of repeating, in any sense; iteration of the same act, word, sound, or idea. • Principle of inclusion and exclusion: The principle of inclusion and exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties while guaranteeing that elements satisfying more than one property are not counted twice. 131 CU IDOL SELF LEARNING MATERIAL (SLM)

6.6 LEARNING ACTIVITY 1. In how many ways can the letters of the word BEAUTY be arranged? 2.From a group of 7 men and 6 women, five persons are to be selected to form a committee so that at least 3 men are there in the committee. In how many ways can it be done? 6.7 UNIT END QUESTIONS A. Descriptive Questions 1. What is Combination? 2. Explain the concept of Permutation 3. State and explain The Exclusion-Inclusion Principle 4. A person has 4 coins if different denominations. What is the number of different sums of money the person can form? 5. How many solutions does x1 + x2 + x3 = 11 have, where x1, x2, and x3 are nonnegative integers with x1 ≤ 3, x2 ≤ 4, and x3 ≤ 6? B. Multiple Choice Questions: 1. In how many ways can we select 6 people out of 10, of which a particular person is not included? a) 10C3 b) 9C5 c) 9C6 d) 9C4 2. Find the number of rectangles and squares in an 8 by 8 chess board respectively. 132 a) 296, 204 b) 1092, 204 c) 204, 1092 d) 204, 1296 CU IDOL SELF LEARNING MATERIAL (SLM)

3. If nPr = 3024 and nCr = 126 then find n and r. a) 9, 4 b) 10, 3 c) 12, 4 d) 11, 4 4. Find the number of ways of arranging the letters of the words DANGER, so that no vowel occupies odd place. a) 36 b) 48 c) 144 d) 96 5. In a colony, there are 55 members. Every member posts a greeting card to all the members. How many greeting cards were posted by them? a) 990 b) 890 c) 2970 d) 1980 6. If 16Pr-1: 15Pr-1 = 16: 7 then find r. a) 10 b) 12 c) 7 d) 8 7. Find the sum of all four-digit numbers that can be formed by the digits 1, 3, 5, 7, 9 without repetition. a) 666700 b) 666600 c) 678860 d) 665500 133 CU IDOL SELF LEARNING MATERIAL (SLM)

8. The property of combination states nCr=? a. nCn-r b. nCn c. nCn+r d. 2nCn-r 9. Number of circular permutations of different things taken all at a time is a. (n – 1)! b. 2n! c. n/2! d. n! 10. There are 20 points in a plane, how many triangles can be formed by these points if 5 are colinear? a) 1130 b) 550 c) 1129 d) 1140 Answers: 1 - c; 2 -b; 3 -a; 4 -a; 5 -c; 6 – a; 7 – b; 8 – a; 9 – d; 10 – a. 6.8 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 • Seymour Lipschutz, Marc Lara’sLipson, Varsha H. Patil, Discrete Mathematics (Schaum's Outlines) | Revised 3rd Edition, McGraw Hill Education; Revised Third edition • C Liu, D. Mohapatra, Elements of Discrete Mathematics: A Computer Oriented Approach | 4th Edition, McGraw Hill Education • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford 134 CU IDOL SELF LEARNING MATERIAL (SLM)

• V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond (Undergraduate Texts in Mathematics), Springer • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin UNIT 7- RECURRENCE RELATIONS 135 Structure 7.0. Learning Objectives 7.1. Introduction 7.2. Nth order recurrence relation with constant coefficients, 7.3. Homogeneous recurrence relations 7.4. Inhomogeneous recurrence relation CU IDOL SELF LEARNING MATERIAL (SLM)

7.5. Summary 7.6. Keywords 7.7. Learning Activity 7.8. Unit End Questions 7.9. References 7.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • ComprehendNth order recurrence relation with constant coefficients, • Enumerate Homogeneous and Inhomogeneous recurrence 7.1 INTRODUCTION A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s). The simplest form of a recurrence relation is the case where the next term depends only on the immediately previous term 7.2 NTH ORDER RECURRENCE RELATION What Is A Recurrence? A recurrence relation for a sequence a0, a1, a2 … is a formula (equation) that relates each term a to certain of its predecessor’s a0, a1 …, an − 1. The initial conditions for such a recurrence relation specify the values of a0, a1, a2 …, an − 1. Let us consider the following example, the recursive formula for the sequence 3, 8, 13, 18, 23 is a1 = 3, an = an − 1 + 5, 2 ≤ n < ∞. Here, a1 = 3 is the initial condition. Similarly, consider the infinite sequence as 3, 7, 11, 15, 19, 23 … which can be defined by the following recursive formula as a1 = 3, an = an − 1 + 4, 2 ≤ n < ∞. Example 1: Find the sequence represented by the recursive formula a1 = 5, an = 2an − 1, 2 ≤ n ≤ 6. Solution: The initial condition is a1 = 5 and n satisfies the condition 2 ≤ n ≤ 6. Thus, a2 = 2a1 = 10, a3 = 2a2 = 20, 136 CU IDOL SELF LEARNING MATERIAL (SLM)

a4 = 2a3 = 40, a5 = 2a4 = 80, a6 = 2a5 = 160. Hence the given recurrence formula defines the finite sequence 5, 10, 20, 40, 80, 160. Finding the General Term of a Sequence from the Recurrence Relation: A. INITIAL CONDITION: This method is best illustrated with the help of following examples as shown below: Example 2: A staircase consists of n steps. A boy walks from the bottom to the top, each time climbing 1 or 2 steps. (a) If n = 10, what is the number of ways in which he can climb up the stairs? (b) If n = 2004, what is the number of ways in which he can climb up the stairs? Solution: Let xnbe the number of ways to climb up a stairs of n steps with each time climbing 1 or 2 steps. So, we have to compute x10and x2004. To climb n steps, we may first climb 1 or 2 steps. In the former case, we are to climb n −1 more steps, and this can be done in ������������−1ways. In the latter case, we are to climb n −2 more steps, and this can be done in ������������−2ways. Therefore, we obtain the recurrence relation ������������ = ������n−1 + ������������−2 Since the recurrence relation for ������������depends on two previous terms, we need two initial conditions i.e.,������1 = 1and ������2 = 2. By direct computation, we can obtain ������10 = 89, thus solving part (a). For part (b) it’s difficult to have direct computation and to find the general term. So, we will solve another example as follows that will help with the (b) part solution as well. Example 3: For positive integer n, let 1 ������(������) = (������������ − ������������) √5 where������and ������(������ > ������)are roots of the equation. 137 CU IDOL SELF LEARNING MATERIAL (SLM)

������2 − ������ − 1 = 0 (a) Find ������ + ������, ������������, ������(1) and ������(2) (b) Show that ������(������ + 2) = ������(������) + ������(������ + 1) (c) Show that ������(������) is an integer for al positive integer n. Solution: (a) The value of ������ + ������ is the sum of roots of the equation ������2 − ������ − 1 = 0, which is 1. Similarly, ������������ is the product of the roots, which is −1. We also have 11 1 ������(1) = (������ − ������) = . √(������ + ������)2 − 4������������ = [(1)2 − 4(−1)] = 1 √5 √5 √5 ������(2) = 1 (������2 − ������2) = 1 (������ − ������)(������ + ������) = ������(1). (������ + ������) = 1 × 1 = 1 √5 √5 Since ������and ������are roots of the equation ������2 − ������ − 1 = 0, we have ������2 − ������ − 1 = 0i.e.,������2 = ������ + 1. Similarly, ������2 = ������ + 1. Consequently, √5������(������ + 2) = ������������+2 − ������������+2 = ������������. ������2 − ������������. ������2 = ������������(������ + 1) − ������������(������ + 1) = (������������+1 − ������������+1) + (������������ − ������������) = √5. ������(������ + 1) + √5. ������(������) Dividing both sides by √5, we get the desired result as follows ������(������ + 2) = ������(������) + ������(������ + 1) (c) Since f (1) and f (2) are integers, and that ������(������ + 2) = ������(������) + ������(������ + 1) so f (n) is an integer for all positive integers n. Incidentally, the f (n) here is precisely the ������������ in the above example. Therefore, the answer to part (b) in above example would be 1 1 + √5 2004 1 − √5 2004 ������2004 = ������(2004) = [( −( 2 ) ] √5 2) where the values of ������and ������ are obtained by solving the equation ������2 − ������ − 1 = 0. 138 B.THE METHOD OF FINITE DIFFERENCES: CU IDOL SELF LEARNING MATERIAL (SLM)

When polynomial is given and we are aware of first few terms, then it is easy to find the general term. For instance, let us consider the following ‘numerical reasoning’ puzzle: 7, 8, 12, 19, 29, , After observing the above sequence, we can easily make out that the difference between successive terms is 1, 4, 7 and 10. Obviously, the next difference would be 13, so the missing term is 42. The next difference is ‘naturally’ 13, because then the ‘second level differences’ would be constantly equal to 3. 7 8 12 19 29 1 4 7 10 333 After two levels of taking differences, we have reached a ‘finite difference’, which is constantly 3. If we regard this as a continuous function, say ������(1) = 7, ������(2) = 8, ������(3) = 12 and so on, and taking differences like this is same like doing differentiation. If the function becomes constant after taking differences twice, it means that the second derivative of the function is constant, and hence the function is a polynomial of degree 2. In this way, the general term of the above sequences to be of degree 2. Let us consider the following expression ������������ = ������������2 + ������������ + ������ For some constants A, B and C, if we put ������1 = 7, ������2 = 8 ������������������������3 = 12, we obtain 7 = ������ + ������ + ������ 8 = ������ + 2������ + ������ 12 = 9������ + 3������ + ������ We have three linear equations in three unknowns, we can solve these for the values of A, B and C. One of the easiest ways to solve the above system of equation is to take successive differences of the equations. For example, if we subtract the first equation from the second and the second from the third, we get the following equation 1 = 3������ + ������ 4 = 5������ + ������ If we again take the difference, we have 3 = 2A, so A= 3/2. Backward substitution yields B = – 7/2 and C = 9. The general term for the sequence is given as ������������ = 23������2 − 7 + 9 2 ������ C. Backtracking Method: CONCEPT: Consider the sequence 1, 4, 9, 16, 25, 36, 49 … which is a sequence of the squares of all positive integers. We can define this sequence by the formula an = n2, 1 ≤ n < ∞. 139 CU IDOL SELF LEARNING MATERIAL (SLM)

So, we have used only positive number to describe the terms of the sequence. Such type of formula is called Explicit formula. Also, the explicit formula an = (−4)n, 1 ≤ n < ∞ describes the infinite sequence −4, 16, −64, 256, … Example 4: Find the explicit formula for the finite sequence 87, 82, 77, 72, 67. Can this sequence be described by a recursive relation? Solution: The explicit formula for the given finite sequence is an = 92 − 5n, n = 1, 2 …. Also, it can be described by the recursive formula a1 = 87, an = an − 1 − 5, 2 ≤ n ≤ 5. To study general properties of sequences, the recurrence relation with initial conditions is solved to get explicit formula. Such an explicit formula is called a solution of the given recurrence relation. CONCEPT: A technique for finding an explicit formula for the sequence defined by a recurrence relation is called backtracking. In this technique, the values of an are back tracked, substituting the values of an − 1, an − 2and so on, till a pattern is clear. Example 5: Find an explicit formula for the recurrence relation a0 = 1, an = an − 1 + 2. Solution: The recurrence relation a0 = 1, an = an − 1 + 2 defines the sequence 1, 3, 5, 7, …. We backtrack the value of an by the substituting the definition of an − 1, an − 2 and so on until there is a pattern. We have an = an − 1 + 2 = an − 2 + 2 + 2 = an − 2 + 2 · 2 = an − 3 + 2 + 2 + 2 = an − 3 + 2 · 3 = an − 4 + 2 + 2 + 2 + 2 = an − 4 + 2 · 4 and so on. Thus, backtracking yields an = an − k + 2k. If we set k = n, then an = an − n + 2 n = a0 + 2 n = 1 + 2 n, which is the required explicit formula. Example 6: Backtrack to find explicit formula for the sequence defined by the recurrence relation 140 CU IDOL SELF LEARNING MATERIAL (SLM)

a1 = 1, an = 3 an − 1 + 1, n ≥ 2. Solution: The recurrence relation defines the sequence 1, 4, 13, 40, …. Backtracking yields an = 3 an − 1 + 1 = 3(3 an − 2 + 1) + 1 = 32·an − 2 + 31 + 1 = 3{3(3 an − 3 + 1) + 1} + 1 = 33 an − 3 + 32 + 31 + 1 = 3[3{3(3 an − 4 + 1) + 1} + 1] + 1 = 34 an − 4 + 33 + 32 + 31 + 1 and so on. The backtracking will end at an = 3k an − k + 3k − 1 + 3k − 2 + … + 32 + 31 + 1. If we set k = n − 1, then we have an = 3n − 1 an − (n − 1) + 3n − 2 + … + 33 + 32 + 31 + 1 = 3n − 1 a1 + 3n − 2 + … + 33 + 32 + 31 + 1 = 3n − 1 + 3n − 2 + … + 33 + 32 + 31 + 1 3������ − 1 3������ − 1 = 3−1 = 2 Hence ������������ = 3������−1is the required explicit formula. 2 7.3 HOMOGENEOUS LINEAR RECURRENCE RELATION: CONCEPT: A linear recurrence relation of order k with constant coefficient is a recurrence relation of the form an = c1 an − 1 + c2 an − 2 + … + ck an − k, ck ≠ 0. For example, 1. The relation ������������ = (−2)������������−1 is a linear homogeneous recurrence relation of order 1. 2. The recurrence relation ������������ = ������������−1 + ������������−2 is a linear recurrence relation of order 2. 141 CU IDOL SELF LEARNING MATERIAL (SLM)

3. The recurrence relation ������������ = 2������������������−1 is not a linear recurrence relation with constant coefficients because the coefficient 2n is not constant. It is a linear homogeneous recurrence relation with non-constant coefficients. 4. The recurrence relation������������ = ������������−1 + 2is not a linear homogeneous recurrence relation because an − an − 1 ≠ 0. It is an inhomogeneous recurrence relation. 5. The recurrence relationan + 7an − 2 = 0is a second order linear recurrence relation with constant coefficients. 6. The recurrence relation������������ = ������������2−1 + ������������−2is not a linear homogeneous relation. Definition: The equationxk = r1 xk − 1 + r2xk − 2 + … + rkof degree k is called the characteristic equation of the linear homogeneous recurrence relationan = r1 an − 1 + r2 an − 2 + … + rk an – kof order k. THEOREM Theorem: If the characteristic equation x2 − r1 x − r2 = 0 of the homogeneous recurrence relationsan = r1 an − 1 + r2 an−2has two distinct roots s1 and s2, then������������ = ������������1������ + ���������������2���where u and v depend on the initial conditions, is the explicit formula for the sequence. (To say “u and v depend on the initial conditions” means that u and v are the solutions of the system of simultaneous equation ������1 = ������������1 + ������������2and ������2 = ������������21 + ������������22) Proof. Since s1 and s2 are roots of the characteristic equation x2 − r1 x − r2 = 0, we have ������12 − ������1������1 − ������2 = 0 (1) ������22 − ������1������2 − ������2 = 0 (2) Let������������ = ������������������ + ������������������������������������������ ≥ 1 (3) 12 It is sufficient to show that (3) defines the same sequence as an = r1an − 1 + r2 an − 2. We have ������1 = ������������1 + ������������2 ������2 = ������������2 + ������������2 12 and the initial conditions are satisfied. Further, ������������ = ������������������ + ������������������ 12 = ������������������−2. ������2 + ������������������−2. ������2 11 22 142 CU IDOL SELF LEARNING MATERIAL (SLM)

= ������������������−2(������1������1 + ������2) + ������������������−2(������1������1 + ������2)[������������������������������(1)a������������(2)] 12 = ������1������������������−1 + ������2������������������−2 + ������1������������������−1 + ������2������������������−2 1 122 = ������1(������������������−1 + ������������������−1) + ������2(������������������−2 + ������������������−2) 12 12 = ������1������������−1 + ������2������������−2 [������������������������������������������������������������������������������������������������������������������(3)] Hence (3) defines the same sequence as an = r1an − 1 + r2an−2. Hence an = us1n + vs2n is the solution to the given linear homogeneous relation. Theorem: If the characteristic equation x2 − r1x − r2 = 0 of the linear homogeneous recurrence relations an = r1 an − 1+ r2 an − 2 has a single root s, then the explicit formula (solution) for the recurrence relation is an = usn+ vnsn, where u and v depend on the initial conditions. Proof. Since s is the root of the characteristic equation, we have s2 − r1s − r2 = 0 (1) Let an = u sn + v n sn , n ≥ 1. (2) It suffices to show that (2) defines the same sequence as an = r1an − 1 + r2an − 2. We have a1 = u s + v s, a2 = u s2 + 2v s2 and the initial conditions are satisfied. Also an = u sn + v n sn = u sn − 2 · s2 + v n sn − 2 · s2 = u sn − 2 (r1s + r2) + vnsn − 2 (r1s + r2) (using (1)) = r1 usn − 1 + r2 usn − 2 + r1 vnsn − 1 + r2 vnsn − 2 143 CU IDOL SELF LEARNING MATERIAL (SLM)

= r1 (usn − 1 + vnsn − 1) + r2(usn − 2 + vnsn − 2) = r1an − 1 + r2an − 2 (using the expression for an − 1 and an − 2 from (2)). Thus (2) defines the same sequence as an = r1an − 1 + r2an−2 and so is the explicit formula for the recurrence relation. Example 1: Find an explicit formula for the sequence defined by the recurrence relationan = an − 1 + 2an−2, n ≥ 2,with the initial conditionsa0 = 1 and a1 = 8. Solution: The recurrence relation an = an − 1 + 2an−2is a linear homogeneous relation of order 2. Its characteristic equation isx2 − x − 2 = 0which yields 1 ± √1 + 8 1 ± 3 ������ = 2 = 2 = 2, −1 Hence, (1) an = u(2)n + v(−1)n and we have a0 = u + v = 1 (given), a1 = 2u − v = 8 (given). Solving for u and v, we have u = 3, v = −2. Hence, an = 3(2)n − 2(−1) n, n ≥ 0is the explicit formula for the sequence. Example 2: Solve the recurrence relation dn = 2dn − 1 − dn−2 with initial conditions d1 = 1.5 and d2 = 3. Solution: The relation dn = 2dn − 1 − dn−2 is a linear homogeneous recurrence relation of order 2. The characteristic equation (or associated equation) for this recurrence relation is x2 − 2x + 1 = 0 which yields 144 CU IDOL SELF LEARNING MATERIAL (SLM)

2 ± √4 − 4 ������ = 2 = 1,1 Thus, the characteristic equation has a multiple root 1. Hence, dn = u · 1n + nv · 1n = (u + nv) · 1n and so d1 = u + v = 1.5 (given), d2 = u + 2v = 3 (given). Solving for u and v, we get u = 0, v = 1.5 and so dn = 1.5n is the explicit formula (homogeneous solution) for the given recurrence relation. Particular Solution of Difference Equation: Definition: The (total) solution of a linear difference equation (linear recurrence relation) an = r1 an − 1 + r2 an−2 + … + rk an−k = f (n), where f (n) is constant or a function of n with constant coefficients is the sum of two parts, the homogeneous solution satisfying the difference equation when the right-hand side of the equation is set to be 0, and the particular solution, which satisfies the difference equation with f (n) on the right-hand side. The particular solution is obtained by the method of inspection because we do not have a general procedure to find particular solution of a given difference equation. A general form of particular integral is set up according to the form of f (n). We will consider the following cases Case I: If f (n) is a polynomial in n of degree m then we take P1 nm + P2 nm − 1 + … + Pm+1as the particular solution of the difference equation. Putting this solution in the given difference equation, the values of P1, P2 …, Pm+1 are determined. Example 3: Find the particular solution of the difference equation an − an − 1 − 2an − 2 = 2n2. Also write down the total solution. Solution: Suppose that the particular solution is of the form P1 n2 + P2 n + P3, (1) where P1, P2 and P3 are constants to be determined. Substituting (1) in the given difference equation, we obtain (P1 n2 + P2 n + P3) − [P1 (n − 1)2 + P2 (n − 1) + P3] − 2[P1 (n − 2)2 + P2 (n − 2) + P3] = 2n2 or P1 n2 + P2 n + P3 − [P1 (n2 + 1 − 2n) + P2 (n − 1) + P3] − 2[P1 (n2 + 4 − 4n) + P2 (n − 2) + P3] = 2 n2 or −2P1 n2 + n (10 P1 − 2 P2) + (−9 P1 + 5 P2 − 2 P3) = 2 n2. 145 CU IDOL SELF LEARNING MATERIAL (SLM)

Comparing coefficients of the powers of n, we have −2 P1 = 2, 10 P1 − 2 P2 = 0, 9 P1 − 5 P2 + 2 P3 = 0, which yield P1 = −1, P2 = −5, P3 = −8. Therefore, the particular solution is −n2 − 5n − 8. The homogeneous solution of this recurrence relation is 3(2)n − 2(−1)n. Hence the total solution is 3.2n − 2(−1)n − n2 − 5n − 8. Example 4: Find the particular solution of the difference equation an + 5an − 1 + 6an − 2 = 3n2 − 2n + 1. Solution: Here the right-hand side is a function of n and it is a polynomial of degree 2. So, suppose that particular solution is of the form P1 n2 + P2 n + P3, (1) where P1, P2 and P3 are to be determined. Substituting (1) in the given difference equation, we get P1 n2 + P2 n + P3 + 5[P1 (n − 1)2 + P2 (n − 1) + P3] + 6[P1 (n − 2)2 + P2 (n − 2) + P3] = 3n2 − 2n + 1, which yields 12P1 n2 − n (34P1 − 12P2) + (29P1 − 17P2 + 12P3) = 3n2 − 2n + 1. Comparing the coefficients of the powers of n we have 12P1 = 3, 34P1 − 12P2 = 2, 29P1 − 17P2 + 12P3 = 1 and so 1 13 71 ������1 = 4 , P2 = 24 , ������������������������3 = 288 Hence, the particular solution is 1 ������2 + 13 ������ + 71 4 24 288 146 CU IDOL SELF LEARNING MATERIAL (SLM)

Case II: If f (n) is a constant, then the particular solution of the difference equation will also be a constant P, provided that 1 is not a characteristic root of the difference equation. Example 5: Find the particular solution of the difference equation an − 4 an − 1 + 5an − 2 = 2. Hence find the total solution of this recurrence relation. Solution: Here f (n) = 2 (constant) and 1 is not characteristic root. So, the particular solution will also be a constant P. Putting in the given recurrence relation of order 2, we have P − 4P + 5P = 2, ⇒ 2P = 2, ⇒ P = 1. Also, the characteristic equation of the given difference equation is x2 − 4x + 5 = 0, whose roots are 4 ± √16 − 20 4 ± 2������ ������ = 2 = 2 = 2 ± ������ Thus, the homogeneous solution is u · (2 + i)n + v · (2 − i)n, n ≥ 0. Hence the total solution of the given difference equation is an = u · (2 + i)n + v · (2 − i)n + 1. Case III: If f (n) is of the form αn, the corresponding particular solution is of the form P αn provided that α is not a characteristic root of the difference equation of order n. Example 6: Find the particular solution of the difference equation an + 5 an − 1 + 4an−2 = 56 · 3n. Hence, find the total solution of this difference equation? Solution: The characteristic equation of the difference equation is x2 + 5x + 4 = 0 whose roots are − 4 and −1. Thus, the homogeneous solution is u (− 4) n + v (−1). Since f (n) = 56 · 3n and 3 is not a characteristic root, the particular solution is of the form P 3n. Substituting this in the difference equation, we get ������. 3������ + 5������(3)������−1 + 4������(3)������−2 = 56. 3������ ⟹ ������(3������ + 5. 3������−1 + 4. 3������−1 = 56. 3������) ⟹ + 5 . 3������ + 4 . 3������ = 56. 3������) ������(3������ 3 9 147 CU IDOL SELF LEARNING MATERIAL (SLM)

54 ⇒ ������ (1 + 3 + 9) = 56 9 + 15 + 4 ⇒ ������ ( 9 ) = 56 ⟹ ������ = 18 Hence the particular solution is 18 · 3n. Case IV: If α is not a characteristic root of the difference equation and f (n) is of the form (c1nm + c2nm − 1 + … + cn+1) αn, then the particular solution is of the form (P1nm + P2nm − 1 + … + Pn+1) αn. Example 7: Find the total solution of the difference equation an − an+1 − 2an − 2 = 3n · 4n. Solution: The characteristic equation of the given difference equation is x2 − x − 2 = 0 Whose roots are 2 and −1. Hence its homogeneous solution is u · 2n + v · (−1) n. Further, f (n) = 3n · 4n and 4 is not a characteristic root of the difference equation. Hence particular solution is of the form (nP1 + P2) 4n. (1) Substituting (1) in the given difference equation, we get (������������1 + ������2)4������ − [(������ − 1)������1 + ������2]4������−1 − 2[(������ − 2)������1 + ������2]4������−2 = 3������. 4������ ⟹ (������������ + P )4������ − 1 [(������ − 1)������ + ������ ]4������ − 2 [(������ − 2)������ + ������ ]4������=3������. 4������ 12 12 12 4 16 11 ������ ������1 ������2 ������2 ������ 4 8) ������ ⟹ ((���5������1���1−) 4+������41������−(���8���1������+1)5+������24) ( 2 + ������2 − − = 3������. ⟹ ������. 4 = 3������. 4������ 4 ������. 4������ 8 28 Comparing coefficients of both sides, we have 24 1 5 96 ������1 = 5 ������������������ 2 ������1 + 8 ������2 = 0 ������������������2 = − 25 Hence the particular solution is (24 ������ − 96) 4������ 5 25 Therefore, the total solution2is4 ������ − 96 4������ ������������ = ������. 2������ + ������(−1)������ + ( ) 5 25 Case V: If α is a characteristic root of multiplicity m−1 and f (n) is of the form 148 CU IDOL SELF LEARNING MATERIAL (SLM)

(c1 np + c2 np − 1 + … + cp+1) αn, the corresponding particular solution of the recurrence relation will be of the form nm − 1(P1 np + P2 np − 1 + … + Pp+1) αn. Example 8: Find the particular solution of the difference equation an − 4an − 1 = 6 · 4n. Solution: The characteristic equation of the given difference equation is x − 4 = 0 and so 4 is a root of multiplicity 1. Therefore, the particular solution is of the formn P · 4n. (1) Substituting (1) in the given difference equation, we get nP · 4n − 4(n − 1)P · 4n − 1 = 6 · 4n ⇒ nP4n − (n − 1)P · 4n = 6 · 4n ⇒ nP − nP + P = 6 ⇒ P = 6. Hence the Particular solution is 6n · 4n, whereas the total solution of the given difference equation is 4n (u + 6n). 7.4 LINEAR INHOMOGENEOUS RECURRENCE RELATION: A linear non-homogenous/inhomogeneous recurrence relation with constant coefficients is a recurrence relation of the form ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) where������1, ������2, … , ������������are real numbers, and ������(������) is a function depending only on n. The recurrence relation ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������, is called the associated homogeneous recurrence relation. This recurrence includes k initial conditions. ������0 = ������0,������1 = ������1, … ������������ = ������������, Example 1: The following recurrence relations are linear nonhomogeneous recurrence relations 1. ������������ = ������������−1 + 2������ 2. ������������ = ������������−1 + ������������−2 + ������2 + ������ + 1 3. ������������ = ������������−1 + ������������−4 + ������! 4. ������������ = ������������−6 + ������2������ THEOREM: Let ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) be a linear non-homogeneous recurrence. Assume the sequence ������������ satisfies the recurrence. Another sequence ������������ satisfies the nonhomogeneous recurrence if and only if ℎ������ = ������������ − ������������ is also a sequence that satisfies the associated homogeneous recurrence is also. Proof: 149 CU IDOL SELF LEARNING MATERIAL (SLM)