= 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 148 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. 149 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 150 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������) ⟹ ������(3������ + 5 3 ������ + 4 3 ������ = 56. 3������) 3. 9. 151 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)P4���)��� 4−������[−(���1��� −[(1������)−������11 )+������������2]+4���������−���1]−4���2��� −[(2������[−(������2−)���2���1)���+��� ������2]4������−2 = 3������. 4������ ⟹ (������������ 12 + ������ ]4������=3������. 4������ 12 12 4 16 1 1 ������1 ������2 ������2 ⟹ ������.4 ������ ((���5���1���−���1)4+������41−������ (8���������1���1+) ������ (2+ 4 − 8 ) = 3������. 4 ������ ⟹ ������. 4������ = 3������. +4 ������2 − 5������2) 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 ���t���o(t−al1s)o������l+ut(io2n4i���s��� − 96 ) 4������ ������������ = ������. 2������ + 5 25 Case V: If α is a characteristic root of multiplicity m−1 and f (n) is of the form 152 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: 153 CU IDOL SELF LEARNING MATERIAL (SLM)
Part1: If ℎ������ satisfies the associated homogeneous recurrence then ������������ satisfies the non-homogeneous recurrence. ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) ℎ������ = ������1ℎ������−1 + ������2ℎ������−2 + ⋯ + ������������ℎ������−������ Now ������������ + ℎ������ = ������1(������������−1 + ℎ������−1) + ������2(������������−2 + ℎ������−2) + ⋯ + ������������(������������−������ + ℎ������−������) + ������(������) Since, ������������ = ������������ + ℎ������ ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) So, ������������ is a solution of the non-homogeneous recurrence. Part2: If������������ satisfies the non-homogeneous recurrence then ℎ������is satisfies the associated homogeneous recurrence. ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������) ������������ − ������������ = ������1(������������−1 − ������������−1) + ������2(������������−2 − ������������−2) + ⋯ + ������������(������������−������ − ������������−������) ℎ������ = ������������ −������������ Since, ℎ������ = ������1ℎ������−1 + ������2ℎ������−2 + ⋯ + ������������ℎ������−������ So, ℎ������is a solution of the associated homogeneousrecurrence. Proposition: Let ������������ = ������1������������−1 + ������2������������−2 + ⋯ + ������������������������−������ + ������(������)be a linear nonhomogeneous recurrence. Assume the sequence ������������satisfies the recurrence. Another sequence an satisfies the non-homogeneous recurrence if and only ifℎ������ = ������������ − ������������is also a sequence that satisfies theassociated homogeneous recurrence. Proof:We already know how to find ℎ������. • For many common������(������), a solution ������������ to the non-homogeneousrecurrence is similar to f(n). • Then you should find solution������������ = ������������ + ℎnto the nonhomogeneousrecurrence that satisfies 154 CU IDOL SELF LEARNING MATERIAL (SLM)
both recurrence andinitial conditions. 155 CU IDOL SELF LEARNING MATERIAL (SLM)
Example 2: What is the solution of the recurrence relation������������ = ������������−1 + ������������−2 + 3������ + 1 ������������������������ ≥ 2 with ������0 = 2and ������1 = 3 ? Solution: Since it is linear non-homogeneous recurrence, ������������ is similar to ������(������) Guess: ������������ = ������������ + ������ ������������ = ������������−1 + ������������−2 + 3������ + 1 ������������ + ������ = ������(������ − 1) + ������ + ������(������ − 2) + ������ + 3������ + 1 ������������ + ������ = ������������ − ������ + ������ + ������������ − 2������ + ������ + 3������ + 1 0 = (3 + ������)������ + (������ − 3������ + 1) ������ = −3, ������ = −10 So ������������ = −3������ − 10 (bn only satisfies the recurrence, it does not satisfy the initial conditions.) 7.5 SUMMARY In this unit, we had discussed how recursive techniques can derive sequences and be used for solving counting problems. The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation. 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. A recurrence relation can also be higher order. To generate sequence based on a recurrence relation, one must start with some initial values. For a first order recursion, one just needs to start with an initial value x0 and can generate all remaining terms using the recurrence relation. For a second order recursion, one needs to begin with two values x0 and x1. Higher order recurrence relations require correspondingly more initial values. 7.6 KEYWORDS: • Recurrence: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). • Initial Condition: an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted t = 0). 156 CU IDOL SELF LEARNING MATERIAL (SLM)
• General Term: a mathematical expression composed of variables and constants that yields the successive terms of a sequence or series when integers are substituted for one of the variables often denoted by k. • Backtracking: A technique for finding an explicit formula for the sequence defined by a recurrence relation is called backtracking. • Finite Difference: The finite difference is the discrete analog of the derivative 7.7 LEARNING ACTIVITY 1. Discuss the difference between finite difference and backtracking method 2. Check that an = 2n + 1 is a solution to the recurrence relation an = 2an-1 - 1 with a1 = 3 7.8 UNIT END QUESTIONS A. Descriptive Questions 1. Find a recurrence relation and initial conditions for 1,5,17,53,161,485… 2. Check that an=2n+1 is a solution to the recurrence relation an = 2an−1 − 1with a1=3. 3. Solve the recurrence relation an=an−1 + n with initial term a0=4. 4. Explain Homogeneous Recurrence Relations 5. Discuss IN Homogeneous Recurrence Relations B. Multiple Choice Questions: 1. Consider the recurrence relation a1=4, an=5n+an-1. The value of a64 is a) 10399 b) 23760 c) 75100 d) 53700 2. Determine the solution of the recurrence relation Fn=20Fn-1 − 25Fn-2 where F0=4 and F1=14. a) an = 14*5n-1 b) an = 7/2*2n−1/2*6n 157 CU IDOL SELF LEARNING MATERIAL (SLM)
c) an = 7/2*2n−3/4*6n+1 d) an = 3*2n−1/2*3n 3. What is the recurrence relation for 1, 7, 31, 127, 499? a) bn+1=5bn-1+3 b) bn=4bn+7! c) bn=4bn-1+3 d) bn=bn-1+1 4. f Sn=4Sn-1+12n, where S0=6 and S1=7, find the solution for the recurrence relation. a) an=7(2n) −29/6n6n b) an=6(6n) +6/7n6n c) an=6(3n+1) −5n d) an=nn−2/6n6n 5. Find the value of a4 for the recurrence relation an=2an-1+3, with a0=6. a) 320 b) 221 c) 141 d) 65 6. The solution to the recurrence relation an=an-1+2n, with initial term a0=2is a) 4n+7 b) 2(1+n) c) 3n2 d) 5*(n+1)/2 7. Determine the solution for the recurrence relation bn=8bn-1−12bn-2 with b0=3 and b1=4. a) 7/2*2n−1/2*6n b) 2/3*7n-5*4n c) 4! *6n d) 2/8n 158 CU IDOL SELF LEARNING MATERIAL (SLM)
8. What is the solution to the recurrence relation an=5an-1+6an-2? a) 2n2 b) 6n c) (3/2) n d) n! *3 9. Determine the value of a2 for the recurrence relation an = 17an-1 + 30n with a0=3. a) 4387 b) 5484 c) 238 d) 1437 10. Determine the solution for the recurrence relation an = 6an-1−8an-2 provided initial conditions a0=3 and a1=5. a) an = 4 * 2n – 3n b) an = 3 * 7n – 5*3n c) an = 5 * 7n d) an = 3! * 5n Answers: 1 -a; 2 - b; 3 -c; 4 - b; 5 - c; 6 – b; 7 – a; 8 – b; 9 – d; 10 – b. 7.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 • Seymour Lipschutz, Marc Lara’sLipson, Varsha H. Patil, Discrete Mathematics (Schaum's Outlines) | Revised 3rd Edition, McGraw Hill Education; Revised Third edition. • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford • V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc. • 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 159 CU IDOL SELF LEARNING MATERIAL (SLM)
UNIT 8- GENERATING FUNCTION 1 Structure 8.0. Learning Objectives 8.1. Introduction 8.2. Closed form expression, 8.3. Properties of G.F. 8.4. Generating Function Models 8.5. Summary 8.6. Keywords 8.7. Learning Activity 8.8. Unit End Questions 8.9. References 8.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • Explain the closed form expression using Generating Function. • Discuss the properties of Generating functions and its models. 8.1 INTRODUCTION An important idea in mathematics is to establish connections between two fields in order to apply knowledge in one field to the other field, or at least take a problem in one field and transform it to a problem in the other field. This idea motivates the idea of a generating function, which establishes a connection between functions of a real variable and sequences of numbers. Generating functions are one of the most surprising and useful inventions in Discrete Math. Roughly speaking, generating functions transform problems about sequences into problems about functions. This is great because we’ve got piles of mathematical machinery for manipulating functions. We can apply generating functions to the machinery of problems about sequences. 8.2 CLOSED FORM EXPRESSION, Generating Function of Sequence: The concept of generating functions is a powerful tool for solving counting problems. Intuitively put, its general idea is as follows. In counting problems, we are often interested in counting the number of 160 CU IDOL SELF LEARNING MATERIAL (SLM)
objects of ‘size n’, which we denote by an. By varying n, we get different values of an. In this way we get a sequence of real numbers a0, a1, a2, … Here our interest is in the sequence of real numbers (a0, a1, a2, …, ar, …), and such function whose domain is the set of nonnegative integers and whose range is the set of real numbers. Expressions like ������ = {������������ }���∞��� is used to denote such sequences, where aris the number of ways to select r objects in some procedure. Example 1: The sequence 0 ������ = {2������}∞������=is0 the sequence (1,2,4,8,16, …, 2r, …); the sequence������ = {������������ }���∞���=0 Where 0 ������������ 0 ≤ ������ ≤4 ������������ = {23 ������������ 5 ≤ ������ ≤ 4 4 ������������������ = 10 ������������ 11 ≤ ������ Thus, B = (0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 3, 4, 4 …) ������ = {������������}∞������=, 0where Cr = r + 1 for each value of r, is the sequence (1, 2, 3, 4, 5…) and the sequence������ = {������������}∞������w=0here for each r dr = r2 is the sequence(0, 1, 4, 9, 16, 25 …) • To the Sequence ������ = {������������}∞������=,0we will assign the symbol ∞ ������(������) = ������0 + ������1������ + ⋯ + ������������������������ = ∑ ������������������������ ������=0 • The expression A (X) is called aformal power series, ai is the coefficient of Xi, the term ai Xi is a term of degree I, and the term a0 X0 = 0 is called the constantterm. • The formal power series ������(������) = ∑∞������������������ ������������is called the generating function for the sequence������ = {������������}∞������=0 • We will use the word ‘formal’ to distinguish between the abstract symbol ������(������) = ∑∞������������������ ������������and the concept of Power series Example 2: The generating functions of example 1 ∞ ������(������) = ∑ 2������������������ ������=0 B (X) = 2 X5 + 2 X6 + 2 X7 + 2 X8 + 2 X9 + 3 X10 + 4 X11 + 4 X12 + … ∞ 161 CU IDOL SELF LEARNING MATERIAL (SLM)
������(������) = ∑(������ + 1)������������ ������=0 162 CU IDOL SELF LEARNING MATERIAL (SLM)
∞ ������(������) = ∑ ������2������������ ������=0 Definition: Given a numeric sequence the series is called the generating function of the sequence. To find the generating function for a sequence means to find a closed form formula for f(x), one that has no ellipses. Example 3: The generating function for the constant sequence, has closed form This is because the sum of the geometric series i (for all x less than 1 in absolute value). Example: Find the generating functions of the following sequences in closed form. Solution. Formally, we can differentiate and integrate a power series term by term. In other words, if 163 CU IDOL SELF LEARNING MATERIAL (SLM)
The same is true for integration in place of differentiation. (a) The generating function is (b) The generating function is Let ������(������) = ∑∞������=0 ������������������������ , ������(������) = ∑∞������=0 ������������������������be two formal power series then we can define following concept as follows: EQUALITY: A (X) = B (X) if and only if an = bn for each n ≥ 0. 164 MULTIPLICATION BY A SCALAR NUMBER C:������������(������) = ∑∞������=0 (������������������)������������ SUM: ������(������) + ������(������) = ∑∞ (������������ + ������������)������������ ������=0 PRODUCT:������(������)������(������) = ∑���∞���=0 ������������������������ CU IDOL SELF LEARNING MATERIAL (SLM)
• Pn Xn is the product of A(X) B (X) which is obtained by taking the sum of all possible products of one term from A(X) and one term from B(X) such that n = sum of the exponents • Thus, this can be accomplished by considering a0 which is a constant term of A (X) and multiply it with the coefficients bn of Xn in B(X) • Proceeding ahead, now coefficient a1 of X in A (X) and multiply it by the coefficient bn – 1 of Xn – 1 in B(X) and so on. • In product we are supposed to use the increasing powers of X in A(X) while decreasing powers of X in B(X) • So, we get Pn = a0 bn + a1 bn – 1 + a2 bn – 2 + … + an b0 = ∑∞������=0 ������������ ������������−������ Thus, A(X)B(X) = a0 b0 +( a0 b1 + a1 b0) X + (a0 b2 + a1 b1 + a2 b0) X2 + …+(a0 bn + a1 bn – 1 + a2 bn – 2 + … + an b0) Xn + … Example 4: If S (X) = a0 + a2X2 + a4X4 + a8X8 and T (X) = b0 + b4X4 + b6X6 + b8X8 (we assume the coefficients for the missing power of X is zero) • Then we can find the coefficient of Xr in S(X) T(X) by considering the powers {X0, X2, X4, X8} from the first factor and the powers {X0, X4, X6, X8} from the second factor such that their sum is r. • For instance, the coefficient of X8 can be obtained by using X0 in the first factor and X8 in the second; X2 in the first factor and X6 in the second. • Thus, the coefficient of X8 in the product S(X) T(X) is such that • P8 = a0b8 + a2b6 + a4b4 + a8b0, because (0, 8), (2, 6), (4, 4), and (8, 0) are the only pairs of exponents of S(X) and T(X) whose sum is 8. • Likewise, the coefficient of X6 in the product is a0 b6 + a2 b4, because there are only two pair of exponents of S(X) and T(X), whose sum is 6. Thus, if a0= 2, a2 = - 5, a4 = 7 + a8 = 3 b0 = 3, b4 = - 6, b6 = 8, b8 = 3 then P8 = (2)(3) + (-5) (8) + (7) (-6) + (3)(3) = - 67, The case where the entire non-zero coefficients are 1 is of special interest. We will have P8 = 4 We can now conclude that the coefficient of X8 in the product is just the number of pairs of exponents whose sum is 8 or in other words the number of integral solutions to the equation e1 + e2 = 8, where e1 and e2 represent the exponents of S(X) and T(X), respectively. 165 CU IDOL SELF LEARNING MATERIAL (SLM)
Remarks: a. The coefficient of Xr in the product (1 + X2 + X4 + X8) (1 + X4 + X6 + X8) is the number of integral solutions to the equation e1 + e2 = r subject to the constraints e1 = 0,2,4,8 and e2 = 0, 4, 6, 8. b. The exponents of the factors in the product reflect the constraint in the equation. c. We can compute the coefficient of Xrby algebra and then discover the number of integral solutions to the equation e1 + e2 =r subject to the constraints; or d. We can compute all the solutions of the equation subject to the constraints and then discover the coefficient of Xr. 8.3 PROPERTIES OF GENERATING FUNCTIONS Most generating functions share four important properties: 1. Under mild conditions, the generating function completely determines the distribution. 2. The generating function of a sum of independent variables is the product of thegenerating functions 3. The moments of the random variable can be obtained from the derivatives of the generating function. 4. Ordinary (pointwise) convergence of a sequence of generating functions corresponds to thespecial convergence of the corresponding distributions. Property 1 is most important. Often a random variable is shown to have a certain distribution by showing that the generating function has a certain form. The process of recovering the distribution from the generating function is known as inversion. Property 2 is frequently used to determine the distribution of a sum of independent variables. By contrast, recall that the probability density function of a sum of independent variables is the convolution of the individual density functions, a much more complicated operation. Property 3 is useful because often computing moments from the generating function is easier than computing the moments directly from the definition. The last property is known as the continuity theorem. Often it is easier to show the convergence of the generating functions than to prove convergence of the distributions directly 8.4 GENERATING FUNCTION MODELS • Let us consider the product of generating function A(X) and B(X), where the exponents of A(X) reflect the constraints on e1and the exponents of B(X) reflect the constraints on e2. • Xr is the coefficient of the product of generating function A(X) B(X) • Assume e1 can only be 0, 1, 9 then let A(X) = 1 + X + X9. If e2 can only be even and 0≤ e2 ≤ 8, then B(X) = 1 + X2 + X4+ X6 + X8 166 CU IDOL SELF LEARNING MATERIAL (SLM)
• And if e1can be any non-negative integer value, then we let 1 + X + X2 + … [ A(X) has infinite number of terms]. Also, if e2 can only take on the integral values like that are multiples of 5, then we let B (X) = 1 + X5 + X10 + … Hence, we can see endless possibilities. Now we can extend the definition of product of formal power series for 3 factors as below: ∞ ������(������) = ∑ ������������������������ ������=0 ∞ ������(������) = ∑ ������������������������ ������=0 ∞ ������(������) = ∑ ������������������������ ������=0 Then ∞ ������(������)������(������)������(������) = ∑ ������������������������ ������=0 where ������������ = ∑ ������������������������������������ ������+������+������=������ Thus, we can find the term PrXr by taking any one term aiXi from A(X), any one term bjXj from B(X) and any one term ckXk from C(X) such that the sum of exponents i + j + k = r. Assume each non-zero coefficient of each formal power series Ai(X) is 1. Then we have the coefficient of Xr in the product A1(X) A2(X) … An(X) indicates the number of integral solutions to the equation e1 + e2 + … + en = r where constraints on each ei is determined by the exponents of the ith factor of Ai(X). Conversely if we are supposed to count the number of non-negative integral solutions to an equation e1 + e2 + … + en = r with constraints on each ei then we can build a generating function A1(X) A2(X) 167 CU IDOL SELF LEARNING MATERIAL (SLM)
… An(X) whose coefficient of Xr is the answer. 168 CU IDOL SELF LEARNING MATERIAL (SLM)
Example 1: Find a generating function for ar = the number of non- negative integral solutions of e1 + e2 + e3 + e4 + e5 = r where 0 ≤ e1 ≤ 3, 0 ≤ e2 ≤ 3, 2 ≤ e3 ≤ 6, 2 ≤ e4 ≤ 6, e5 is odd, and 1 ≤ e5 ≤ 9. Let A1(X) = A2(X) = 1+ X + X2 + X3, A3(X) = A4(X) = X2 + X3 + X4 + X5 + X6 and A5(X) = X + X3 + X5 + X7 + X9. Thus, the generating function we want is A1(X) A2(X) A3(X) A4(X) A5(X) = (1+ X + X2 + X3)2 (X2 + X3 + X4 + X5 + X6 )2 (X + X3 + X5 + X7 + X9). Example 2: Find a generating function for ar = the number of non- negative integral solutions of e1 + e2 +…+ en = r where 0 ≤ ei ≤ 1. Let Ai(X) = 1 + X for each i = 1, 2, …, n. Thus, the generating function we want is A1(X) A2(X) … An(X) = (1 + X) n. As per the binomial theorem the answer to above is C (n, r) – the coefficient of Xr term. Example 3: Find the coefficient of X16 in (1 + X4+ X8 )10. The only solution to e1 + e2 + … + e10 = 16 where ei = 0, 4, 8 are those with four 4’s, no 8’s and six 0’s or two 8’s, no 4’s and eight 0’s; or two 4’s, one 8, and seven 0’s. Thus, the coefficient is 10 10 10 10 10 (4)+(2)+8(2)=(4)+9(2) Example 4: Build a generating function for determining the number of ways of making change for a dollar bill in pennies, nickels, dimes, quarters, and half- dollar pieces. Which coefficient do we want? We can find the coefficient of X100 in the product of (1 + X + X2 + … + X100) (1 + X5 + X10 + … + X100) (1 + X10 + X20 + … + X100) (1 + X25 + X50 + X75 + X100) (1 + X50 + X100). Example 5: Find a generating function for the sequence ������ = {������������}∞������=w0here 1 if 0 ≤ r ≤ 2 A = 3 if 3 ≤ r ≤ 5 0 if r ≥ 6 169 CU IDOL SELF LEARNING MATERIAL (SLM)
Solution: 1 + X + X2 + 3X3 + 3 X4 + 3X5 8.5 SUMMARY A generating function is just a different way of writing a sequence of numbers. Definition - Let (an) n ≥0 be a sequence of numbers. The generating function associated to this sequence is the series A(x) = ∑������≥0 ������������������������ Also, if we consider a class A of objects to be enumerated, we call generating function of this class the generating function A(x) = ∑������≥0 ������������������������ where an is the number of objects of size n in the class. One use for generating functions is get closed formulas for sequences which are defined recursively in terms of previous terms. Important concepts in Power Series: Equality:A (X) = B (X) If and Only If An = Bn For Each N ≥ 0. Multiplication by A Scalar NumberC:������������(������) = ∑∞ (������������������)������������ ������=0 SUM: ������(������) + ������(������) = ∑∞ (������������ + ������������)������������ ������=0 PRODUCT:������(������)������(������) = ∑���∞���=0 ������������������������ Properties of Generating Functions 170 Most generating functions share four important properties: CU IDOL SELF LEARNING MATERIAL (SLM)
1. Under mild conditions, the generating function completely determines the distribution. 171 CU IDOL SELF LEARNING MATERIAL (SLM)
2. The generating function of a sum of independent variables is the product of thegenerating functions 3. The moments of the random variable can be obtained from the derivatives of the generating function. 4. Ordinary (pointwise) convergence of a sequence of generating functions corresponds to thespecial convergence of the corresponding distributions. Generating Function Model: If we are supposed to count the number of non-negative integral solutions to an equation e1 + e2 + … + en = r with constraints on each ei then we can build a generating function A1(X) A2(X) … An(X) whose coefficient of Xr 8.6 KEYWORDS • Generating function:A Generating function is a way of encoding an infinite sequence of numbers (an) by treating them as the coefficients of a formal power series. • Closed-form a closed-form expression is a mathematical expression expressed using a finite number of standard operations. • Constant term: is a term in an algebraic expression that has a value that is constant or cannot change, because it does not contain any modifiable variables • Power series, in mathematics, an infinite series that can be thought of as a polynomial with an infinite number of terms, such as 1 + x + x2 + x3 +⋯. • Scalar: A scalar is an element of a field which is used to define a vector space 8.7 LEARNING ACTIVITY 1. Explain basic prerequisites for Generating Function. 2. Find the generating function for the sequence {an} defined by a0 = 1 and an= 8an−1 + 10n−1 for n ≥ 1 Then find explicit formula for an. 8.8 UNIT END QUESTIONS 172 A. Descriptive Type Questions CU IDOL SELF LEARNING MATERIAL (SLM)
1. What is Generating Function? 2. Explain the closed form of Generating Function with example. 3. Discuss the properties of Generating Function 4. Explain the Generating Function Models. 5. Prove that the generating function for 1,1, 1, 1, ... is 1 1−������ B. Multiple Choice Questions: 1. What is the sequence depicted by the generating series 4 + 15x2 + 10x3 + 25x5 + 16x6+⋯? a) 10, 4, 0, 16, 25, … b) 0, 4, 15, 10, 16, 25, c) 4, 0, 15, 10, 25, 16, d) 4, 10, 15, 25, … 2. What is the generating function for the sequence 1, 6, 16, 216,.? a) (1+6x)x3 b) 1(1−6x) c) 1(1−4x) d) 1-6x2 3. What is multiplication of the sequence 1, 2, 3, 4,… by the sequence 1, 3, 5, 7, 11,….? a) 1, 5, 14, 30,… b) 2, 8, 16, 35,… c) 1, 4, 7, 9, 13,… d) 4, 8, 9, 14, 28,… 4. What will be the sequence generated by the generating function 4x/(1-x)2? a) 12, 16, 20, 24,… b) 1, 3, 5, 7, 9,… c) 0, 4, 8, 12, 16, 20,… d) 0, 1, 1, 3, 5, 8, 13,… 173 CU IDOL SELF LEARNING MATERIAL (SLM)
5. What is the recurrence relation for the sequence 1, 3, 7, 15, 31, 63,…? a) an = 3an-1−2an+2 b) an = 3an-1−2an-2 c) an = 3an-1−2an-1 d) an = 3an-1−2an-3 6. What is multiplication of the sequence 1, 2, 3, 4,… by the sequence 1, 3, 5, 7, 11,….? a) 1, 5, 14, 30,… b) 2, 8, 16, 35,… c) 1, 4, 7, 9, 13,… d) 4, 8, 9, 14, 28,… 7. What is the generating function for the generating sequence A = 1, 9, 25, 49,…? a) 1+(A-x2) b) (1-A)-1/x c) (1-A)+1/x2 d) (A-x)/x3 8. What is the generating function for the sequence with closed formula an=4(7n)+6(−2)n? a) (4/1−7x)+6! b) (3/1−8x) c) (4/1−7x)+(6/1+2x) d) (6/1-2x)+8 9. Suppose G is the generating function for the sequence 4, 7, 10, 13, 16, 19,…, the find a generating function (in terms of G) for the sequence of differences between terms. a) (1−x)G−4/x b) (1−x)G−4/x3 c) (1−x)G+6/x d) (1−x)G−x2 10. Find the sequence generated by 1/1−x2−x4.,assume that 1, 1, 2, 3, 5, 8,… has generating function 1/1−x−x2. a) 0, 0, 1, 1, 2, 3, 5, 8,… b) 0, 1, 2, 3, 5, 8,… 174 CU IDOL SELF LEARNING MATERIAL (SLM)
c) 1, 1, 2, 2, 4, 6, 8,… d) 1, 4, 3, 5, 7,… Answers: 1 – c; 2 – b ; 3 – a ; 4 – c ; 5 - b; 6 – a ; 7 – b; 8 – c; 9 – a; 10 – a. 8.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 • 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 • V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc • Miklos Bona Introduction to Enumerative and Analytic Combinatorics (DiscreteMathematics and Its Applications) 2nd Edition, Chapman and Hall/CRC • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 175 CU IDOL SELF LEARNING MATERIAL (SLM)
UNIT 9- GENERATING FUNCTION 2 Structure 9.0. Learning Objectives 9.1. Introduction 9.2. Solution of recurrence relation using G.F, 9.3. Solution of combinatorial problem using G.F. 9.4. Summary 9.5. Keywords 9.6. Learning Activity 9.7. Unit End Questions 9.8. References 9.0 LEARNING OBJECTIVES: After studying this unit, you will be able to: • Outline the solution of Recurrence relation using Generating Function by translating a recurrence relation for the terms of a sequence into an equation involving a generating function. • Discuss to prove combinatorial identities using Generating Function. 9.1 INTRODUCTION In combinatorics, there are two powerful tools that help us to solve many problems, namely recurrence relation and generating function. Recurrence relation arises naturally in definitions of sequences or when we try to break the problem into cases, some of which is similar to the original problem. Generating functions are closely related to sequences, and can be used to solve recurrence relations and other kinds of problems such as enumeration problems and proving identities involving sequences. A generating function is a (possibly infinite) polynomial whose coefficients correspond to terms in a sequence of numbers an. Due to their ability to encode information about an integer sequence, generating functions are powerful tools that can be used for solving recurrence relations. Techniques such as partial fractions, polynomial multiplication, and derivatives can help solve the recurrence relations. 176 CU IDOL SELF LEARNING MATERIAL (SLM)
9.2 SOLUTION OF RECURRENCE RELATION USING G.F, Solving Recurrence Relation: We will consider the following example to clarify the different methods. 1. Solve the recurrence relation an = an – 1 + ƒ (n) for n ≥ 1 by substitution. a1=a0 + ƒ (1) a2 =a1 + ƒ (2) = [a0 + ƒ (1)] + ƒ (2) a3 =a2 + ƒ (3) = [a0 + ƒ (1) + ƒ (2)] + ƒ (3) . . . an = a0 + ƒ (1) + ƒ (2) + …+ ƒ (n) = ������0 + ∑∞ ������������(������) Moreover generally, if c is a constant then we can solve a0 = can- 1 + ƒ (n) for n ≥ 1 in the same way: a1=c a0 + ƒ (1) a2= c a1 + ƒ (2) = c [c a0 + ƒ (1)] + ƒ (2) = c2 a0 + c ƒ (1) + ƒ (2) a3 =c a2 + ƒ (3) = c [c2 a0 + c ƒ (1) + ƒ (2)] + ƒ (3) = c3 a0 + c2 ƒ (1) + c ƒ (2) + ƒ (3) . . . an= c an – 1 + ƒ (n) = c [ cn - 1 a0 + cn – 2 ƒ (1) + …+ c ƒ (n – 2) + ƒ (n – 1) + ƒ (n) = cn – 1a0 + cn – 1 ƒ (1) + cn – 2 ƒ (2) + …+ c ƒ (n – 1) + ƒ (n) Or 177 CU IDOL SELF LEARNING MATERIAL (SLM)
������ ������������ = ������������������0 + ∑ ������������ ������(������) ������=1 Solution by Generating Functions: First, we will try to understand the shifting properties of generating functions: • If ������(������) = ∑∞������=0 ������������������������generates the sequence (a0, a1, a2, …), • Then X A(X) generates the sequence (0, a0, a1, a2, …); • X2 A(X) generates the sequence (0,0, a0, a1, a2, …); • In general, Xk A(X) generates the sequence (0, 0…0, a0, a1, a2…) where there are k zeros before a0. • If A(X) is the generating function for the sequence (a0, a1, a2…), then multiply A(X) by X amounts to shifting the sequence one place to the right and inserting a zero in front. • Similarly, if we multiply by Xk amounts to shifting the sequence k positions to the right and inserting k zeros in front. • The above process can be demonstrated in the formal power series expression as follows: ∞∞ ������������������(������) = ������������ ∑ ������������������������ = ������������ ∑ ������������+������ ������=0 ������=0 • If we replace n + k by r and then we will have n = r – k so we have new equation after substitutionas ∑∞������=������ ������������−������������������ which signifies that it generates the sequence {������������ }���∞���=0where 0 = b0 =b1 = … = bk- 1, bk = a0, bk + 1 = a1 and in general br = ar – k if r ≥ k. Thus, the nth term in the new sequence is obtained from the old sequence by replacing an = an – k if n ≥ k and by 0 if n < k. • For instance, we know that 1 / (1 – X) =∑∞������=0 ������������generates the sequence (1, 1, 1, …), that is, the sequence {������������}∞������=w0here an = 1 for each n ≥ 0. • Thus, ∞∞ ������ 1 − ������= ∑ ������������+1 = ∑������������ ������=0 ������=1 Generates (0, 1, 1, 1, …) and ������2 ∞ ∞ 1 − ������ = ∑ ������������+2 = ∑������������ ������=0 ������=2 Generates (0,0, 1, 1, 1, …). Similarly, 178 CU IDOL SELF LEARNING MATERIAL (SLM)
∞∞ 1 (1 − ������)2 = ∑ ������(������ + 1, ������)������������ = ∑(������ + 1)������������ ������=0 ������=2 Generates the sequence (1, 2, 3, 4 …) so that ∞∞ ������ (1 − ������)2 = ∑(������ + 1)������������+1 = ∑ ������������������ ������=0 ������=1 Generates the sequence {������}∞������=0= (0, 1, 2, 3, 4…). [∑ ∞ ������������������describes the coefficient of X0 is 0 because the sum is taken from r = 1 to ∞, but still, we ������=1 get same conclusion] So, we can write ∞∞ ������ (1 − ������)2 = ∑ ������������������ ������������������������������ = ∑ ������������������ ������=1 ������=0 Both the above expression indicates that the coefficient of ������0 is zero. Similarly, ������2 ∞ ∞ (1 − ������)2 = ∑(������ + 1)������������+2 = ∑(������ − 1)������������ ������=0 ������=2 Generates the sequence (0, 0, 1, 2, 3, 4…) that is the sequence {������������ }���∞���=0where br = r – 1 if r ≥ 2 but 0 = b0 = b1 . Since, the expression br = r – 1 equal to zero when r = 1, we can write the expression ������2 = ∑∞ (������ − 1)������������as∑∞ (������ − 1)������������. ������=2 ������=1 (1−������)2 Following the above procedure, 1 = ∞ + 2, ������)������������ = ∞ (������ + 2)(������ + 1) ������������ − ������)3 2 (1 ∑ ������(������ ∑ ������=0 ������=0 Generates the sequence {(������ + 2)(������ + 1) ∞ 1.2 2.3 3.4, } =( 2 2 2,2 , … ), ������=0 and therefore, 179 CU IDOL SELF LEARNING MATERIAL (SLM)
generates 2∞ (1 − ������)3 = ∑(������ + 2)(������ + 1)������������ ������=0 {(������ + 2)(������ + 1)}∞������=0 = (1.2,2.3,3.4, …). But then, 2������ ∞∞ (1 − ������)3 = ∑(������ + 2)(������ + 1)������������+1 = ∑(������ + 1)(������)������������ ������=0 ������=1 generates the sequence (0, 1.2,2.3,3.4,…). Now since ������������ = (������ + 1)(������) equals 0 where r = 0, we can write 2������ ∞∞ (1 − ������)3 = ∑(������ + 1)(������)������������ = ∑(������ + 1)(������)������������ ������=1 ������=0 so that 2������ generates {(������ + 1)(������)}∞ (1−������)3 ������=0. Similarly, 2������2 ∞ ∞∞ (1 − ������)3 = ∑(������ + 2)(������ + 1)������������+2 = ∑(������)(������ − 1)������������ = ∑(������)(������ − 1)������������ ������=0 ������=2 ������=0 generates the sequence (0,0,1.2,2.3,3.4,…) and the last sum can be taken from 0 to ∞ because the coefficient r ( r – 1) is 0 when r = 0, 1. In this way, we can combine these results to obtain generating functions for other sequences. For example, 2������ − (1 ������ = ������(1 + ������) (1 − ������)3 − ������)2 (1 − ������)3 generates the sequence {(������ + 1)(������) − ������}∞ = {������2}∞ = (0,1,4,9, … ) ������=0. ������=0. In the similar way, ∞ ∞ (1 − ������)4 1 180 CU IDOL SELF LEARNING MATERIAL (SLM)
= ∑ ������(������ + 3, ������)������������ = ∑ (������ + 3)(������ + 2)(������ + 1) ������������ 6 ������=0 ������=0 181 CU IDOL SELF LEARNING MATERIAL (SLM)
generates {(������+3)(������+2)(������+1) ∞ 6 {( )( )( )}∞ ������ + 3 ������ + 2 ������ +1 ������=0; 6 } ; (1−������)4 generates ������=0 6������ = ∞ + 3)(������ + 2)(������ + 1)������������+1 (1 − ������)4 ∑(������ ������=0 ∞ = ∑(������ + 2)(������ + 1)(������)������������ ������=1 ∞ = ∑(������ + 2)(������ + 1)(������)������������ ������=0 generates{(������ + 2)(������ + 1)(������)}∞ ������=0. ; ������������������ ∞ 6������2 = ∑(������ + 3)(������ + 2)(������ + 1)������������+2 (1 − ������)4 ������=0 ∞ = ∑(������ + 1)(������)(������ − 1)������������ ������=1 ∞ = ∑(������ + 1)(������)(������ − 1)������������ ������=0 generates{(������ + 1)(������)(������ − 1)}∞ ������=0. Since (������ + 3)(������ + 2)(������ + 1) = ������3 + 6������2 + 11������ + 6 then ������3 = (������ + 3)(������ + 2)(������ + 1) − 6������2 − 11������ − 6 so that {������3}∞ is gener���a���=t0ed by 6 6(������)(1 + ������) − 11 (1 ������ − (1 6 = ������(1 + 4������ +������2) (1 −������)4 − (1 − ������)3 − ������)2 − ������) (1 − ������)4 In similar way we can find the generating functions for the sequences{������4}∞ , {������5}∞ and so on. ������=0 ������=0 2. If ������(������) = ∑∞������=0 ������������������������ generates the sequence (a0, a1, a2, …), then 182 CU IDOL SELF LEARNING MATERIAL (SLM)
������(������) − ������0 = ∑∞ ������������������������generates the sequence (0, a1, a2, …) and in general ������=1 183 CU IDOL SELF LEARNING MATERIAL (SLM)
������(������) − ������0 − ������1������ − ⋯ − ������������−1������������−1 = ∑∞ ������=������ ������������������������generates( 0, 0, …,0, ak, ak+ 1…), where there are k zeros before ak.But when we divide it by powers of X shifts the sequence to the left like for example, ������(������)−������0−������1������ generates ������(������)−������0 = ∑∞������=1 ������ ������������−1 generates the sequence (������ , ������ , ������ , … ); ������ ������2 ������ 123 (������2, ������3, ������4, … ); and inn general for ������ ≥ 1, ������(������)−������0−������1������−������⋯������ −������k−1������������−1generates(������ ������, ������������+1 , ������������+2 , … ). Similarly, if we substitute n – k = r and the expression ������(������)−������0−������1������−⋯−������������−1������������−1 = ������������ ∑ ∞ ������������������������−������becomes ∑∞������=0 ������������+������������������ which generates the sequence(������������, ������������+1, ������������+2, … ). Other way ������=������ round, the term ������������ in the original sequence is replaced by ������������+������ for each n, indicating that the sequence has been shifted k places to the left. Example 1: Solve the recurrence relation ������������ − 7������������−1 + 10������������−2 = 0 forn ≥ 0 Solution: We will number the steps of the procedure. 1. Let ������(������)= ∑∞������=0 ������������������������. 2. Next multiply each term in the recurrence relation by Xn and sum from 2 to ∞: ∞∞ ∞ ∑ ������������������������ − 7 ∑ ������������−1������������ + 10 ∑ ������������−2������������ = 0 ������=2 ������=2 ������=2 3. Replace each infinite sum by an expression from the table of equivalent expressions: [A(X) – a0 – a1X] – 7 X [A(X) – a0] + 10 X2 [A(X)] 4. Then simplify: A(X) (1 – 7 X + 10 X2) = a0 + a1X – 7 a0X or ������(������) = ������0 + (������1 − 7������0)������ = ������0 + (������1 − 7������0)������ 1 − 7������+ 10������2 (1 − 2������)(1 − 5������) 5. Decompose A(X) as a sum of partial fractions: ������(������) = 1 ������1 + 1 ������2 − 2������ − 5������ 184 CU IDOL SELF LEARNING MATERIAL (SLM)
where C1 and C2 are constants, as yet undetermined. 6. Express A(X) as a sum of familiar series: ������(������) = 1 ������1 + 1 ������2 ∞∞ − 2������ − 5������ = ������1 ∑ 2������������������ + ������2 ∑ 5������������������ ������=0 ������=0 7. Express an as the coefficient of Xn in A(X) and in the sum of the other series: an = C1 2n + C2 5n 8. Now the constants C1 and C2 are uniquely determined once values for a0 and a1 are given. For example, if a0 = 10 and a1 = 41, we may use form of the general solution an = C1 2n + C2 5n , and let n = 0 and n = 1 to obtain the equations C1 + C2 = 10 and 2C1 + 5C2 = 41, which determine the values C1 = 3 and C2 =7. The unique solution of the recurrence relation is an= (3)2n + (7)5n THEOREM: If {������������}∞������=0 is a sequence of numbers which satisfy the linear recurrence relation with constant coefficients an + c1 an - 1 +… + ck an - k = 0, where ������������ ≠ 0, and n ≥ k, then the generating function ������(������) = ∑∞������=0 ������������������������ equals P(X) / Q(X), where P(X) = a0 + (a1 + c1 a0 ) X + … +( ak- 1 + c1 ak - 2 + … + ck – 1 a0) Xk – 1 and Q(X) = 1 + c1 X + … + ck Xk. Conversely, If P(X) and Q(X) are polynomials given, where P(X) has degree less than k, there is a sequence {������������}∞������=w0 hose generating function is A(X) = P(X) / Q(X). The sequence {������������}∞������=s0atisfies a linear homogenous recurrence relation with constant coefficients of degree k, where the coefficients of the recurrence relation are the coefficients of Q(X). In fact, if Q(X) = b0 + b1 X + … + bkXk where������0 ≠ 0 and ������������ ≠ 0then ������(������) = ������ (1 + ������1 ������ +⋯+ ������������ ������������) 0 ������0 ������0 185 CU IDOL SELF LEARNING MATERIAL (SLM)
= ������0(1 + ������1������ + ⋯ + ������������������������ ) where ci = bi/ b0 for i ≥ 1. Then ������(������ = 1 ������(������) ������(������) = ) ������0 1 + ������1������ + ⋯ ������������������������ ������(������ ) and the coefficient of A(X) are discovered by using partial fractions and the factors of 1 + c1 X + … + ck Xk. then the recurrence relation satisfied by the coefficients of A(X) is an + c1 an- 1 + … + ck an – k = 0. Example 2: Solve the following recurrence relations using generating functions. a. an – 9an- 1 + 20an- 2 = 0 for n ≥ 2 and a0 = – 3, a1 = – 10 b. an – 5an- 1 + 6an- 2 = 0 for n ≥ 2 and a0 = 1 , a1 = – 2 c. an – 3an- 2 + 2an- 3 = 0 for n ≥ 3 and a0 = 1, a1 = 1, a2 = 2. d. an + an- 1 – 16 an- 2+ 20an- 3 = 0 for n ≥ 3 and a0 = 1, a1 = 1, a2= - 1 Solution: a. an = 2.5n – 5.4n b. A(X) = [1 – 7 X] / [1 – 5X + 6 X2] = [ 5 / 1 – 2X] – [ 4 / 1 – 3X]; an= 5(2n) – 4(3n) c. an = 8 / 9 – 6/ 9 n + 1/ 9 ( - 2 )n d. A(X) = [X / 1 + X – 16X2 + 20 X3] = −2/49 + (1 97/4 − 1 5/49 1 − 2������ − 2������)2 + 5������ ������������ = −2/49(2������) + 7/49(������ + 1)(2������) − 5/49(−5)������ 9.3 SOLUTION OF COMBINATORIAL PROBLEM USING G.F. The problem is to calculate 186 CU IDOL SELF LEARNING MATERIAL (SLM)
for all values of n: To accomplish this we construct the generating function 187 CU IDOL SELF LEARNING MATERIAL (SLM)
This is a formal inÖnite sum. No convergence is implied. The generating function for just one type, say Ak, looks like Thus we can select n objects in 1 way if Ak allows that. Here are a few examples of generating functions for just one type Note that the only coefficients we see are 1, the terms that don’t appear are the ones with coe¢ cient 0 and correspond to selections that the type does NOT allow. In the Örst case the type allows for 0 or 1 object to be selected. In the second case any number of objects. In the third case at least r objects. In the fourth case only an odd number of objects. Finally, the last case is when the type allows a number of objects that is a prime number. Going back to our general problem we deÖne the generating function for each type as The claim is that the original generating function is the product of the generating functions for the types: 188 CU IDOL SELF LEARNING MATERIAL (SLM)
The product on the right can be multiplied out more easily if we use different indices for n in each sum. When manipulating such sums, you should work with them as if they were multiple integrals with n1, ..., nk being the variables and be happy that no inÖnitesimals are messing up the calculations Thus, we must show that but this is simply our recurrence formula At this point we seem to have achieved absolutely nothing. When we get to the examples below, we shall see that the advantage of this method is that we really can work with generating functions as functions 9.4 SUMMARY A generating function is a (possibly infinite) polynomial whose coefficients correspond to terms in a sequence of numbers an. Due to their ability to encode information about an integer sequence, generating functions are powerful tools that can be used for solving recurrence relations. When generating functions are used to solve counting problems, they are usually considered to be formal power series. One potential benefit to the generating function approach for nonhomogeneous equations is that it does not require determining an appropriate form for the particular solution. However, the method of generating functions often requires that the resulting generating function be expanded using partial fractions. 189 CU IDOL SELF LEARNING MATERIAL (SLM)
9.5 KEYWORDS • Coefficient: is a number multiplied by a variable • Sequence: is an enumerated collection of objects in which repetitions are allowed and order matters. • Decompose:To breaking something into parts, that together are the same as the original. • Series: is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. • Determine: To fix or define the position, form, or configuration of. 9.6 LEARNING ACTIVITY 1. Solve the recurrence relation hn = 5hn−1 −6hn−2 with i. c. h0 = 1 and h1 =−2. 2. Find the generating function for the Fibonacci numbers {Fn}, using the initial conditions F0 = F1 = 1, and the recurrence relation Fn+2 = Fn+1 + Fn. 9.7 UNIT END QUESTIONS A. Descriptive Type Question 1. Discuss the concept of Recurrence Relation 2. Explain Recurrence Relations using Generating Function 3. What do you understand by solution of combinatorial problem using G.F.? 4. Explain shifting properties of Generating functions 5. Explain solution of recurrence relation by substitution B. Multiple choice Questions: 1. How many ways are there to make a sum of 10, using exactly one element from each of the following two sets: {2,3,6,7} and {3,4,5,8}? a) 3 ways of making 10 b) 5 ways of making 10 190 CU IDOL SELF LEARNING MATERIAL (SLM)
c) 7 ways of making 10 d) 9 ways of making 10 2. Find the generating function for the face value of 1 die a) R1(x) = x1- x2+ x3 + x4 - x5 + x6 b) R1(x) = x1 - x2+ x3 + x4 + x5 + x6 c) R1(x) = x1+ x2+ x3 + x4 + x5 + x6 d) R1(x) = x1+ x2+ x3 + x4 - x5 - x6 3. In general, Xk A(X) generates the sequence (0, 0…0, a0, a1, a2…) where there are zeros before a0. a) k-1 b) k c) k + 2 d) 2k 4. In the sum of terms, the highest degree of a term is the degree of the . a) recurrence b) Largest number c) Smallest number d) Denominator 5. What is the degree of linear recurrence? a) 0 b) 1 c) -2 d) 3 6. If the recurrence (without initial conditions) applies to the sequence consisting only of 0's then the recurrence is a) Normal b) Linear c) Standard d) homogeneous 191 CU IDOL SELF LEARNING MATERIAL (SLM)
7. If all the terms in a recurrence involve only previous terms and a constant multiplier, then the recurrence has a). Constant coefficients b). Linear coefficient c). Ascending coefficient d). Descending coefficient 8. A recurrence of order k needs initial terms to define it completely a). k b). k/2 c). 2k d). 2k+1 9. If A(X) is the generating function for the sequence (a0, a1, a2…), then multiply A(X) by amounts to shifting the sequence one place to the right and inserting a zero in front. a). 2X b). X c). 3X d). X/4 10. If P(X) and Q(X) are polynomials given, where P(X) has degree less than k, there is a sequence {������������}∞������=0whose generating function is a). A(X) = P(X) / Q(X). b). A(X) = P(X) / 2Q(X). c). A(X) = 2P(X) / Q(X). d). A(X) = P(X) + Q(X). 192 CU IDOL SELF LEARNING MATERIAL (SLM)
Answers: 1 – a; 2 – c; 3 –d; 4 – a; 5 – b; 6 – d; 7 – a; 8 – a; 9 – b; 10 – a. 9.8 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. • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond (Undergraduate Texts in Mathematics), Springer • 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 193 CU IDOL SELF LEARNING MATERIAL (SLM)
UNIT 10- TREES STRUCTURE 10.0. Learning Objectives 10.1. Introduction 10.2. Definition 10.2.1 Basic Terminology: 10.3. Types of tree (rooted, binary), 10.4. Properties of trees, 10.5. Binary search tree, 10.6. Tree traversing (preorder, inorder, postorder). 10.7. Summary 10.8. Keywords 10.9. Learning Activity 10.10. Unit End Questions 10.11. References 10.0 LEARNING OBJECTIVES: After studying this unit, you will be able to: • Explain the concept of trees • State the types and properties of trees • Enumerate tree traversing 10.1 INTRODUCTION A powerful way to represent relationships between objects in visual form can be done using a mathematics structure called a graph. One uses dots called vertices to represent objects and line segments which join the dots, called edges, to represent some relationship between the object which the dots represent. Tree is a discrete structure that represents hierarchical relationships between individual elements or nodes. A tree in which a parent has no more than two children is called a binary tree. A tree or general trees is defined as a non-empty finite set of elements called vertices or nodes having the property that each node can have minimum degree 1 and maximum degree n. It can be partitioned into n+1 disjoint subset such that the first subset contains the root of the tree and remaining n subsets includes the elements of the n subtree. 194 CU IDOL SELF LEARNING MATERIAL (SLM)
10.2 DEFINITION • A tree is a simple graph G such that there is a unique simple nondirected path between each pair of vertices of G. • A rooted tree is a tree in which there is one designated vertex, called a root. • A rooted tree is a directed tree if there is a root from which there is a directed path to each vertex. In such case there is exactly one such root. • The level of a vertex v in a rooted tree is the length of the path to v from the root. • A tree T with only one vertex is called a trivial tree; otherwise, it is a nontrivial tree. 10.2.1 Basic Terminology: 1. Root- • The first node from where the tree originates is called as a root node. • In any tree, there must be only one root node. • We can never have multiple root nodes in a tree data structure. Example- Fig 10.1: Representation of Root node 195 CU IDOL SELF LEARNING MATERIAL (SLM)
Here, node A is the only root node. 2. Edge- • The connecting link between any two nodes is called as an edge. • In a tree with n number of nodes, there are exactly (n-1) number of edges. Example- Fig 10.2: Representation of Edge 3. Parent- • The node which has a branch from it to any other node is called as a parent node. • In other words, the node which has one or more children is called as a parent node. • In a tree, a parent node can have any number of child nodes. Example- 196 CU IDOL SELF LEARNING MATERIAL (SLM)
Fig 10.1: Representation of Parent node Here, • Node A is the parent of nodes B and C • Node B is the parent of nodes D, E and F • Node C is the parent of nodes G and H • Node E is the parent of nodes I and J • Node G is the parent of node K 4. Child- • The node which is a descendant of some node is called as a child node. • All the nodes except root node are child nodes. Example- 197 CU IDOL SELF LEARNING MATERIAL (SLM)
Search
Read the Text Version
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241