1 00:00:03,600 --> 00:00:09,493 Now we're going to take a look at the use of generating functions to address the 2 00:00:09,493 --> 00:00:13,496 important tasks that we brought up in the last lecture. 3 00:00:13,496 --> 00:00:19,390 programs many of which can be casts as recursive programs or algorithms 4 00:00:19,390 --> 00:00:23,818 immediately lead to mathematical models of their behavior called recurrence 5 00:00:23,818 --> 00:00:28,538 relations and so we need to be able to solve recurrence relations in order to be 6 00:00:28,538 --> 00:00:32,384 able to analyze algorithms. And so now, I'll take a look at how you 7 00:00:32,384 --> 00:00:35,590 use generating functions to solve recurrence relations. 8 00:00:35,590 --> 00:00:41,129 and it's pretty much a algorithmic process that is we want to we want hate 9 00:00:41,129 --> 00:00:44,101 to use a meat grinder, but it gives the idea. 10 00:00:44,101 --> 00:00:49,032 We want to put in a recurrence relation and we want to turn the crank and we 11 00:00:49,032 --> 00:00:54,031 want to get out a sequence. We want to get out of a simple expression 12 00:00:54,031 --> 00:00:58,759 for what it represents. and it's pretty much a general procedure 13 00:00:58,759 --> 00:01:02,340 that we can always follow. I'll give many examples. 14 00:01:02,340 --> 00:01:08,799 So first thing is we're going to make the recurrence valid for all values of N and 15 00:01:08,799 --> 00:01:13,757 the, it's easy to do that and I'll show you in many, in the examples. 16 00:01:13,757 --> 00:01:19,090 Then, multiply both sides of the recurrence by z to the n and sum on n. 17 00:01:19,090 --> 00:01:24,584 so it's an equation that's valid for all n so that we can do that. 18 00:01:24,584 --> 00:01:28,324 And usually, we make it just for nonnegative n. 19 00:01:28,324 --> 00:01:35,345 then that'll give us some sums but some of those sums will involve the, an, an 20 00:01:35,345 --> 00:01:41,069 unknown generating function and maybe some well-known generating functions. 21 00:01:41,069 --> 00:01:48,090 the end result will be an equation that's the OGF corresponding the recurrence has 22 00:01:48,090 --> 00:01:52,059 to satisfy. so then, what we need to do is to solve 23 00:01:52,059 --> 00:01:56,232 that equation to get an explicit formula for the OGF. 24 00:01:56,232 --> 00:02:02,566 a lot of times we can go ahead and do that and we'll get plenty of examples. 25 00:02:02,566 --> 00:02:08,751 the initial conditions play a role. and then we'll expand the OGF to find the 26 00:02:08,751 --> 00:02:12,096 coefficients. So, the recurrence corresponds to a 27 00:02:12,096 --> 00:02:14,974 sequence. the OGF is a way to represent the 28 00:02:14,974 --> 00:02:17,976 sequence. We'll use the refer, recurrence to find 29 00:02:17,976 --> 00:02:22,917 out what the OGF is and then we'll expand to get the coefficients which is the 30 00:02:22,917 --> 00:02:25,920 goal. That's, that's what we're trying to find. 31 00:02:25,920 --> 00:02:31,493 so let's look at the example. Now, in the case of linear recurrences 32 00:02:31,493 --> 00:02:36,221 with constant coefficients the procedure really is an algorithm. 33 00:02:36,221 --> 00:02:42,500 We always can get a solution and actually people have implemented this in symbolic 34 00:02:42,500 --> 00:02:46,592 mass systems. So so here's an example from the previous 35 00:02:46,592 --> 00:02:50,543 lecture. so that's a recurrence that is defined 36 00:02:50,543 --> 00:02:57,670 for n bigger than 2 with the initial conditions a 0 to 0 and a1 = 1. 37 00:02:57,670 --> 00:03:05,240 so the first thing is make it valid for all n and so it's all n greater equal to 38 00:03:05,240 --> 00:03:08,895 0. And so, all we do is use a kronecker 39 00:03:08,895 --> 00:03:14,638 delta notation. so for one this thing and you assume that 40 00:03:14,638 --> 00:03:22,090 for negative indices of 0. so a0 = 0 so that would be 0, that'd be 41 00:03:22,090 --> 00:03:24,635 0. So for a1, we'd have to add a1, so, when 42 00:03:24,635 --> 00:03:28,133 n is 1 we want to add 1. That's what that kronecker delta is at, 43 00:03:28,133 --> 00:03:32,983 the right there. A0 is expressed then in terms of a's with 44 00:03:32,983 --> 00:03:37,594 negative indices which is 0, so its okay a0 = 0. 45 00:03:37,594 --> 00:03:43,240 So that's how recurrence is valid for all n greater equal 0. 46 00:03:43,240 --> 00:03:47,809 So now, we multiply by z to the n and sum on n. 47 00:03:47,809 --> 00:03:52,467 Sum n greater than equal to 0, A to the n, z to the n. 48 00:03:52,467 --> 00:03:59,234 That's our generating function, A(z), that we're going to use to represent this 49 00:03:59,234 --> 00:04:04,946 sequence a sub n. For the first term on the right-hand side 50 00:04:04,946 --> 00:04:09,692 it's sum an - 1, z to the n. Change n to n1 + 1 throws out A(z). 51 00:04:09,692 --> 00:04:15,564 So that's 5zA(z). And for the second term we change n to n 52 00:04:15,564 --> 00:04:23,705 plus 2 in the, in the sum and throw out Az^2 that's minus 6z^2, a of z. 53 00:04:23,705 --> 00:04:30,271 And the kronecker delta term, that's sum all n but that thing is only 54 00:04:30,271 --> 00:04:36,574 one when n = 1. So, that's z to the n, in that case, is just z. 55 00:04:36,574 --> 00:04:42,001 So that's an equation that generating function has to satisfy. 56 00:04:42,001 --> 00:04:47,405 and that's a, [COUGH] easy equation to solve with some 57 00:04:47,405 --> 00:04:51,484 algebra. so that is, it's just A of z is just z 58 00:04:51,484 --> 00:04:59,242 over 1 minus 1 - 5z + 6z^2. that's again equation that, that generic 59 00:04:59,242 --> 00:05:04,196 function has to satisfy. so, that's generating function, now we 60 00:05:04,196 --> 00:05:09,460 want to extract coefficients because our goal is to find an expression for an. 61 00:05:09,460 --> 00:05:12,616 so how we are going to extract coefficients? 62 00:05:12,616 --> 00:05:17,780 Well, in the case of ratio of two polynomials, it's not difficult it's 63 00:05:17,780 --> 00:05:23,590 technique knows as partial fractions where we factor the polynomial and the 64 00:05:23,590 --> 00:05:27,607 denominator. and we know that our solution must be at 65 00:05:27,607 --> 00:05:33,274 this form, because if you cross multiply then in the denominator, you get the 66 00:05:33,274 --> 00:05:36,215 right polynomial because you've factored it. 67 00:05:36,215 --> 00:05:41,738 And then, the numerator you've got two equations and two unknowns you have to 68 00:05:41,738 --> 00:05:49,360 have c0 + c1 = 0 and you have to have the 2c0 + 3c1 = -1. 69 00:05:49,360 --> 00:05:55,234 So that is, those unknowns have to satisfy those two simultaneous equations 70 00:05:55,234 --> 00:06:02,463 and that's just what we got before and the solution is z0 = 1 and z1 = -1. 71 00:06:02,463 --> 00:06:08,563 and so, that now expresses the generating function as a difference between two 72 00:06:08,563 --> 00:06:14,889 geometric sums and those we know how to expand, it's 3 to the N minus two to the 73 00:06:14,889 --> 00:06:18,432 N. So that's step by step given a recurrence 74 00:06:18,432 --> 00:06:24,299 we can get the solution that is a simple expression for the coefficients and 75 00:06:24,299 --> 00:06:29,600 that's going to work in every case. Now, there's complications that arise. 76 00:06:29,600 --> 00:06:35,254 Let's look at a more complicated example. sometimes and, and this works for 77 00:06:35,254 --> 00:06:41,686 actually any linear recurrence, because you get a polynomial and you can always 78 00:06:41,686 --> 00:06:47,020 factor a polynomial. So, so let's look at this one, 5 an minus 79 00:06:47,020 --> 00:06:54,705 1 minus 8 an-2 plus 4n-3. Same procedure to make these initial 80 00:06:54,705 --> 00:06:59,724 conditions satified. I start at 0 and work up and find that I 81 00:06:59,724 --> 00:07:06,311 have to add a delta n1 and a minus delta n2 in order to make it valid for all 82 00:07:06,311 --> 00:07:10,339 that. Then, when you multiply by z to the n and 83 00:07:10,339 --> 00:07:15,685 sum on end you get this equation on the generating function. 84 00:07:15,685 --> 00:07:19,079 5zA(z) - 8z^2A(z) + 4z^3A(z)3 + z - z^2.2. 85 00:07:19,079 --> 00:07:25,529 And again, now just using algebra, now we have an explicit expression for the 86 00:07:25,529 --> 00:07:30,111 generating function. It's the ratio of two polynomials. 87 00:07:30,111 --> 00:07:37,154 And ratio of two polynomials, partial fractions works, you have multiple terms. 88 00:07:37,154 --> 00:07:43,870 in this case, there's the [COUGH] the root 1/2 has multiplicity 2 89 00:07:43,870 --> 00:07:49,330 and that means just that, that polynomial 90 00:07:49,330 --> 00:07:57,042 is I got three roots and then actually in this case one of the roots cancels with 91 00:07:57,042 --> 00:08:04,349 the numerator so we have A(z) = z / (1-2z)^2 but that's one that we know, 92 00:08:04,349 --> 00:08:11,250 that's a generating function that we already derived by differentiating the 93 00:08:11,250 --> 00:08:17,340 geometrican scaling and that says that a sub n = n2^n-1. 94 00:08:17,340 --> 00:08:22,753 Again, just algebra to find an explicit representation for the generating 95 00:08:22,753 --> 00:08:28,004 function and then expand. now, it turns out that if you have roots 96 00:08:28,004 --> 00:08:34,387 of multiplicity 3, you'll get terms of the form n^22, something to the n and so 97 00:08:34,387 --> 00:08:38,184 forth. and there's other things that can happen, 98 00:08:38,184 --> 00:08:44,405 but it's just properties of polynomials. so, for example, you could get complex 99 00:08:44,405 --> 00:08:48,077 roots. So here's an example where the roots are 100 00:08:48,077 --> 00:08:55,022 complex. Again, this is the same set up we have a third order linear equation 101 00:08:55,022 --> 00:09:00,826 constant coefficients. we've got three initial conditions. 102 00:09:00,826 --> 00:09:08,915 apply, do the deltas to make it valid for all n multiply by z^n n and sum on n and 103 00:09:08,915 --> 00:09:15,226 then do algebra and then that gives a again a ratio of two polynomials. 104 00:09:15,226 --> 00:09:21,116 The degree of the polynomial is equal to the degree of the recurrence. 105 00:09:21,116 --> 00:09:28,942 in this case what happens is there is +z z^2 is one of the roots, one of the 106 00:09:28,942 --> 00:09:32,208 factors of the [COUGH] denominator. 107 00:09:32,208 --> 00:09:38,127 And again the numerator cancels so what do we do with 1 + z^2? 108 00:09:38,127 --> 00:09:45,245 well, we can factor it with complex and find out that A(z) is a half, 1 / 1 - i 109 00:09:45,245 --> 00:09:53,107 of z plus 1 over 1 plus i of z and we can go ahead and expand that and get this 110 00:09:53,107 --> 00:09:57,630 representation. It's i to the n plus minus i to the n or 111 00:09:57,630 --> 00:10:04,807 you can factor out an i to the n. and even though, i appears in this 112 00:10:04,807 --> 00:10:09,648 solution if, when you do the math the 113 00:10:09,648 --> 00:10:13,151 i never appears as a member of the sequence. 114 00:10:13,151 --> 00:10:19,997 because when i is odd this thing cancels and when n is odd, this thing cancels to 115 00:10:19,997 --> 00:10:23,977 0. and when n is even, then you go between 1 116 00:10:23,977 --> 00:10:27,480 and -1 between because of the i^22 or i^4.4. 117 00:10:27,480 --> 00:10:34,616 so that's a rather strange oscillating sequence, but it comes out immediately 118 00:10:34,616 --> 00:10:41,673 from our process of our algorithmic process of finding sequence corresponding 119 00:10:41,673 --> 00:10:46,725 to a given recurrence. It's a nice example, because it shows the 120 00:10:46,725 --> 00:10:53,541 origin of the oscillations that we often see when we're studying algorithms or 121 00:10:53,541 --> 00:10:58,432 combinatorial structure. Those oscillations are modeled in 122 00:10:58,432 --> 00:11:04,016 mathematics really, in this case, by just the square root of -1. 123 00:11:04,016 --> 00:11:10,598 square root of -1^2 is -1, and to the fourth power is +1, and that's 124 00:11:10,598 --> 00:11:16,425 really reflected in this sequence. and it's going to be maybe not so easy to 125 00:11:16,425 --> 00:11:22,321 uncover oscillations without using complex and as we'll see complex analysis 126 00:11:22,321 --> 00:11:28,011 plays a fundamental role in analytic combinatorics when we get into advanced 127 00:11:28,011 --> 00:11:31,217 methods. [COUGH] okay. 128 00:11:31,217 --> 00:11:35,050 So here's a summary. and then, this is just a math with 129 00:11:35,050 --> 00:11:40,015 unknowns just so we can state a theorem. And it's kind of a complicated looking 130 00:11:40,015 --> 00:11:44,917 theorem, but next time we'll show that we don't really need all this detail. 131 00:11:44,917 --> 00:11:50,196 but it's worthwhile to fully state this theorem, because the method that we've 132 00:11:50,196 --> 00:11:55,727 talked about really leads right to a proof of this theorem that's not that 133 00:11:55,727 --> 00:11:59,183 abstract. it's just a matter of turning the crank. 134 00:11:59,183 --> 00:12:04,746 So what we know is that if you've got a [INAUDIBLE] order linear recurrence with 135 00:12:04,746 --> 00:12:10,020 constant coefficients so that you just have [INAUDIBLE] terms on the right-hand 136 00:12:10,020 --> 00:12:13,004 side. It's going to be a linear combination of 137 00:12:13,004 --> 00:12:16,195 t terms. and it depends on the roots of the 138 00:12:16,195 --> 00:12:21,469 polynomial that's induced by what happens when you get, when you multiply by 139 00:12:21,469 --> 00:12:25,632 [INAUDIBLE] and do the algebra. You're always going to get this 140 00:12:25,632 --> 00:12:29,934 polynomial, 1 - x1 minus like that in the 141 00:12:29,934 --> 00:12:33,820 denominator. and it depends on the multiplicity of 142 00:12:33,820 --> 00:12:39,283 those roots so if you've got r roots, where the multiplicity is m sub i. 143 00:12:39,283 --> 00:12:44,802 So if you add up all the multiplicities you get t, then your solution is 144 00:12:44,802 --> 00:12:51,425 depending on the multiplicity it's going to be, for every root you got a the, that 145 00:12:51,425 --> 00:12:57,019 root to a power plus n times that root to a power all the way up to the, the 146 00:12:57,019 --> 00:13:00,330 multiplicity and that has a total of t terms. 147 00:13:00,330 --> 00:13:06,806 and again I'm not expect, not expecting people to follow really every detail of 148 00:13:06,806 --> 00:13:12,400 this, but, you, you can get the idea that we can, actually write down a full 149 00:13:12,400 --> 00:13:18,622 solution to linear recurrence and generating functions give us this proof. 150 00:13:18,622 --> 00:13:25,069 And the constants involved can always be determined from the initial conditions 151 00:13:25,069 --> 00:13:30,766 and that's using partial fractions and solving simultaneous equations. 152 00:13:30,766 --> 00:13:36,913 And again, this is all automatic and people have implemented this process in 153 00:13:36,913 --> 00:13:42,236 symbolic algebra systems. so actually, nowadays you can type in 154 00:13:42,236 --> 00:13:47,436 recurrences and get the solution. and don't forget, your solution might 155 00:13:47,436 --> 00:13:52,754 introduce, might involve periodic behavior that's introduced by the complex 156 00:13:52,754 --> 00:13:57,866 roots, so it might not be the case to prove to be able to prove that even a 157 00:13:57,866 --> 00:14:00,730 recurrence like this converges to a limit. 158 00:14:00,730 --> 00:14:06,730 but it's all very straightforward and well understood mathematically. 159 00:14:06,730 --> 00:14:09,772 Now, what about the analysis of algorithms? 160 00:14:09,772 --> 00:14:15,641 For quicksort, we had this rather complex recurrence that was our starting point 161 00:14:15,641 --> 00:14:21,147 for the analysis of quicksort. Can we use generating functions to solve 162 00:14:21,147 --> 00:14:25,566 the quick sort recurrence? and, and the answer of course is that we 163 00:14:25,566 --> 00:14:28,391 can. to make life easiest, we'll first 164 00:14:28,391 --> 00:14:33,318 multiply both sides by n, although you can get it done without doing that. 165 00:14:33,318 --> 00:14:40,494 so now we have a recurrence where we're not dividing by n and then multiply by Z 166 00:14:40,494 --> 00:14:45,052 to the N, and sum. over now we sum for N bigger than or 167 00:14:45,052 --> 00:14:49,550 equal to 1 and that's just because the CK-1 to 168 00:14:49,550 --> 00:14:54,517 save us a few terms. so that's multiplying by Z to the N and sum and now 169 00:14:54,517 --> 00:14:58,955 we got to look at each one of the terms and see what we have. 170 00:14:58,955 --> 00:15:04,320 what do, what do we have on the left there? well, if we define the generating 171 00:15:04,320 --> 00:15:09,685 function for the sequence of interest to be C of Z equals sum C sub n, Z to the N. 172 00:15:09,685 --> 00:15:14,521 That is if you differentiate that multiplied by Z, that's what you get. 173 00:15:14,521 --> 00:15:20,085 So that one is C prime of Z and there's a factor of Z all the way through that's 174 00:15:20,085 --> 00:15:24,208 divided out. This one is two 175 00:15:24,208 --> 00:15:32,180 [COUGH] 2z over 1-EQ. and again that's right out of the table. 176 00:15:32,180 --> 00:15:40,248 and then a factor of z divides out. And this one is a convolution, it's 1 / 1 177 00:15:40,248 --> 00:15:45,569 - z * z of z. so I, I skipped just a very few steps 178 00:15:45,569 --> 00:15:51,092 here involving indexes that go to 0 and involving dividing by z. 179 00:15:51,092 --> 00:15:56,993 But you can convince yourself quite easily that that ordinary differential 180 00:15:56,993 --> 00:16:03,650 equation is the result of the [COUGH] simply evaluating the sums to get the 181 00:16:03,650 --> 00:16:07,660 equation that the generating function has to satisfy. 182 00:16:07,660 --> 00:16:14,390 So, that's ordinary differential equation and it's completely well, well-defined 183 00:16:14,390 --> 00:16:20,591 and so now we need to know about solving differential equations, to get this 184 00:16:20,591 --> 00:16:26,489 solved, and I don't want to give a course on solving differential equations. 185 00:16:26,489 --> 00:16:32,010 I just point this out as an example for people who do know that 186 00:16:32,010 --> 00:16:37,560 it's possible to solve it just by considering the equation without the 187 00:16:37,560 --> 00:16:41,596 extra term. and figuring out that, what you need to 188 00:16:41,596 --> 00:16:47,435 do is, solve that prob, that problem. in that case, that problem, the solution 189 00:16:47,435 --> 00:16:51,904 is 1 / 1 - z^2.2. so if we didn't have this constant term, 190 00:16:51,904 --> 00:16:57,526 the solution would be 1 / 1 - z^2. [INAUDIBLE] differentiate that, it's the 191 00:16:57,526 --> 00:17:02,500 same thing as if you multiply by one over one - z and multiply by 2. 192 00:17:02,500 --> 00:17:08,802 and then, what you do is multiply, by that, or divide by that factor, which 193 00:17:08,802 --> 00:17:14,092 wides up by multiplying. and it's really, actually analogous, and 194 00:17:14,092 --> 00:17:20,239 it is totally analogous to what we did when solving for sorted linear 195 00:17:20,239 --> 00:17:26,307 reccurences, where we try to find something to multiply it by to make it 196 00:17:26,307 --> 00:17:31,831 that a telescope, this is kind of similar. and this comes out to be a 197 00:17:31,831 --> 00:17:36,908 simple equation in terms of the function, 1 / 1. 198 00:17:36,908 --> 00:17:42,212 z^2, c of z. so if you differentiate that you get this 199 00:17:42,212 --> 00:17:46,945 thing so and that's then equivalent to our equation. 200 00:17:46,945 --> 00:17:54,534 so two that's 2 over 1-z and now, we can just integrate that simple thing if that 201 00:17:54,534 --> 00:18:01,389 shows that c of z times order 1-c squared is equal of n of all of that which is two 202 00:18:01,389 --> 00:18:07,538 log over 1-z and that's a solution. and so that's solving the differential 203 00:18:07,538 --> 00:18:11,739 equation to get an explicit representation for the generating 204 00:18:11,739 --> 00:18:13,365 function. not too bad. 205 00:18:13,365 --> 00:18:18,853 It's a standard differential equation. And now, we want to extract coefficients 206 00:18:18,853 --> 00:18:24,477 to find the number of compares taken by quicksort, but that's easily done. we've 207 00:18:24,477 --> 00:18:28,406 seen that one that's the example that we did for an 208 00:18:28,406 --> 00:18:31,930 exercise. It's 2 N plus 1, H N plus 1 minus 1. 209 00:18:31,930 --> 00:18:36,279 So, OGFs can solve recurrences even as 210 00:18:36,279 --> 00:18:43,934 complicated as the quicksort recurrence. there's many other examples of solutions 211 00:18:43,934 --> 00:18:47,240 of recurrences using OGFs in the book.