1 00:00:03,420 --> 00:00:07,303 Okay, now we're going to talk about. Telescoping a recurrence. 2 00:00:07,303 --> 00:00:11,073 that's a basic technique for solving recurrences. 3 00:00:11,073 --> 00:00:15,529 So let's get into general techniques for solving a recurrence. 4 00:00:15,529 --> 00:00:20,465 so this type of recurrence is called a linear first-order recurrence. 5 00:00:20,465 --> 00:00:25,537 So, that means that there's [COUGH] the coefficients are constant. 6 00:00:25,537 --> 00:00:29,513 and there's only one term, on the right hand side. 7 00:00:29,513 --> 00:00:35,271 So this is a very, simple recurrence. and what I want to show with this example 8 00:00:35,271 --> 00:00:39,590 is that recurrences like this always telescope to a simple sum. 9 00:00:39,590 --> 00:00:45,800 so what we do is, take the same equation for N minus one and apply it. 10 00:00:45,800 --> 00:00:48,926 So applied the same equation for N minues one. 11 00:00:48,926 --> 00:00:54,084 And, we did this in the middle of the quick service example before. 12 00:00:54,084 --> 00:00:57,522 So, if AN equals AN minus one plus N, then AN minus one equals N minus two plus 13 00:00:57,522 --> 00:01:01,162 N minus one. And the thing is we can do the same 14 00:01:01,162 --> 00:01:03,224 thing. We just do it again. 15 00:01:03,224 --> 00:01:05,682 AN minus two has got to equal N minus three plus N minus two. 16 00:01:05,682 --> 00:01:12,184 And the idea is to keep doing that and it is called telescoping until we get down 17 00:01:12,184 --> 00:01:13,370 to 80. so, 18 00:01:13,370 --> 00:01:16,921 when we have ao here, then we're left with A1. 19 00:01:16,921 --> 00:01:22,841 or we just threw out a one. Every time we throw out a thing that's 20 00:01:22,841 --> 00:01:28,602 equal to the ones on the left. So, that's a proof that, A sub N is equal 21 00:01:28,602 --> 00:01:32,470 to A0 plus, sum from one goes from K to N of K. 22 00:01:32,470 --> 00:01:39,730 that's the solution to the recurrence, well maybe it's not that helpful a 23 00:01:39,730 --> 00:01:44,459 recurrence because we have to know how to evaluate the sum. 24 00:01:44,459 --> 00:01:50,790 in this case the value of the sum is half N plus one times N, but in general we 25 00:01:50,790 --> 00:01:55,439 might have a more complicated bit of mathematics to do. 26 00:01:55,439 --> 00:02:02,091 And however you evaluate the sum it's easy to check that it's a solution to the 27 00:02:02,091 --> 00:02:06,980 recurrence N plus one times N over two is equals to N times N minus one over two 28 00:02:06,980 --> 00:02:13,430 plus N. we put in a 2N over two and just add N the minus one 29 00:02:13,430 --> 00:02:17,810 becomes a plus one. So that's a a quick solution and now what 30 00:02:17,810 --> 00:02:22,668 it says is, that if we have a first order linear recurrence we can, 31 00:02:22,668 --> 00:02:26,090 that's equivalent to being able to evaluate a sum. 32 00:02:26,090 --> 00:02:30,916 now the challenge is how are we going to evaluate sums? 33 00:02:30,916 --> 00:02:39,377 and there's some elementary discrete sums that turn up that we have to be able to 34 00:02:39,377 --> 00:02:43,058 do. And, and many of these, are familiar 35 00:02:43,058 --> 00:02:48,875 So anyway, we'll catalog'em. and in the book there's a discussion of 36 00:02:48,875 --> 00:02:51,967 of, of how we know these things to be true. 37 00:02:51,967 --> 00:02:57,341 But many of these are familiar. So that's the standard sum of a geometric 38 00:02:57,341 --> 00:03:01,096 series. sum k goes from zero less than N of X to 39 00:03:01,096 --> 00:03:03,820 the K, is one minus X to the N over one ninus X. 40 00:03:03,820 --> 00:03:08,092 and similarly arithmetic series that's the one that we just did. 41 00:03:08,092 --> 00:03:10,961 that's another way to write that u, value. 42 00:03:10,961 --> 00:03:16,509 now we use less than instead of less than or equal so it's N times N minus one over 43 00:03:16,509 --> 00:03:20,080 two and that's the binomial coefficient N choose two. 44 00:03:20,080 --> 00:03:28,253 and that's actually can be generalized to do a sum this is the case, M equals zero. 45 00:03:28,253 --> 00:03:36,513 and if we generalize that to any value of M that's the sum of a binomial on the on 46 00:03:36,513 --> 00:03:41,469 the upper coefficient is M plus one choose M plus one. 47 00:03:41,469 --> 00:03:47,495 [COUGH] the binomial theorem is like summing on the lower index binomial 48 00:03:47,495 --> 00:03:51,708 coefficient. and then you can X, that's what X plus Y 49 00:03:51,708 --> 00:03:56,502 to the N is equal to. so that's another sum that comes up. 50 00:03:56,502 --> 00:04:02,531 here's one that turned up for quick sort, that's the harmonic numbers, the sum of 51 00:04:02,531 --> 00:04:06,741 one over K. from K goes from one to N is defined to 52 00:04:06,741 --> 00:04:12,747 be the harmonic number H of N. in that's a discreet sum that comes up 53 00:04:12,747 --> 00:04:19,124 very often in the analyses of algorithms. and then, there's more complicated ones 54 00:04:19,124 --> 00:04:22,610 that involve more complicated sumons, sumans. 55 00:04:22,610 --> 00:04:25,947 So, this one's called a vandermon convolution. 56 00:04:25,947 --> 00:04:32,175 When you have two binomial coefficients N choose K and M choose T minus K, summed 57 00:04:32,175 --> 00:04:36,968 on the lower. if you sum those you just add across and 58 00:04:36,968 --> 00:04:41,591 get M plus sum N choose T. So those are examples of elementary 59 00:04:41,591 --> 00:04:46,049 discrete sums. and maybe people are familiar with these 60 00:04:46,049 --> 00:04:52,992 from some math course or another. and we talk about some of them in in the 61 00:04:52,992 --> 00:04:56,207 book. But really, if you want to learn about 62 00:04:56,207 --> 00:05:00,665 how to do discrete sums. see [INAUDIBLE] volume one or the 63 00:05:00,665 --> 00:05:04,320 [INAUDIBLE] book that's referenced in the text. 64 00:05:04,320 --> 00:05:11,011 So from, from this point on I'm going to kind of assume at least these and maybe 65 00:05:11,011 --> 00:05:16,770 some of some others that can easily be derived from elementary analysis. 66 00:05:16,770 --> 00:05:26,260 okay so but still that is not a very rich class of recurrences that we talked about 67 00:05:26,260 --> 00:05:32,191 how to solving. with the [COUGH] linear first-order 68 00:05:32,191 --> 00:05:36,739 recurrence. because the coefficient of AN minus one 69 00:05:36,739 --> 00:05:40,698 was one. And so, first example where it gives us a 70 00:05:40,698 --> 00:05:45,522 richer class of recurrences is when this coefficient is not one. 71 00:05:45,522 --> 00:05:51,283 so here is a simple example, A sub N equals two, A sub N minus one plus two to 72 00:05:51,283 --> 00:05:54,595 the N. Again, with a zero equals zero we always 73 00:05:54,595 --> 00:06:00,283 have to specify everything that should be for n greater than zero where a zero 74 00:06:00,283 --> 00:06:02,146 equals zero. so that, 75 00:06:02,146 --> 00:06:07,038 doesn't immediately telescope. We could apply the same equation for AN 76 00:06:07,038 --> 00:06:13,239 minus one but then we have to take care of the two and we get two complicated 77 00:06:13,239 --> 00:06:17,580 nested parentheses. To avoid that in this case what we do is 78 00:06:17,580 --> 00:06:22,980 just divide by two to the N. If we divide every term in this equation 79 00:06:22,980 --> 00:06:27,160 by two to the N, then the two to the N becomes one. 80 00:06:27,160 --> 00:06:30,721 and then we do get an equation that telescopes. 81 00:06:30,721 --> 00:06:36,633 Because the first term on the right hand side is the same as the first term on the 82 00:06:36,633 --> 00:06:39,838 left hand side, except with N replaced by N minus one. 83 00:06:39,838 --> 00:06:43,257 So now we can go ahead and telescope this thing. 84 00:06:43,257 --> 00:06:47,958 And in this case every time we go down one, it throws out a one. 85 00:06:47,958 --> 00:06:54,440 and so, we get down to A0 after N times. so that's a proof by telescoping that A 86 00:06:54,440 --> 00:06:59,481 sub N over two to the N is equals to N. and then just multiply by two to the N, 87 00:06:59,481 --> 00:07:02,900 and that's a proof that A sub N equals N, two to the N. 88 00:07:02,900 --> 00:07:08,904 So that's a, a solution by using a summation factor to turn a, linear first 89 00:07:08,904 --> 00:07:12,282 order recurrence into one that telescopes. 90 00:07:12,282 --> 00:07:17,011 and then again, you can check by if you don't believe the 91 00:07:17,011 --> 00:07:21,064 solution. And you should always do this even if you 92 00:07:21,064 --> 00:07:26,844 do believe it, is check that it works. so if we put N two to the N and 2N minus 93 00:07:26,844 --> 00:07:29,932 two to the N minus one plus 2 to the N do the math. 94 00:07:29,932 --> 00:07:34,114 that's two times 2N, that's one, that's N2 to the N. 95 00:07:34,114 --> 00:07:37,870 And then we have a minus 2N plus 2N. So that checks. 96 00:07:37,870 --> 00:07:43,540 so that's a solution to a recurrence with a constant first coefficient. 97 00:07:43,540 --> 00:07:48,254 But now the challenge is how do we find the summation factor? 98 00:07:48,254 --> 00:07:54,293 it turns out to be not too difficult. actually, there's two different ways. 99 00:07:54,293 --> 00:07:59,227 but the main one that we're going to use is shown right here. 100 00:07:59,227 --> 00:08:04,677 It works even when the coefficient is not a constant but some sequence. 101 00:08:04,677 --> 00:08:09,351 All we do is divide both side by the product XN, XN minus one, XN minus two 102 00:08:09,351 --> 00:08:13,298 down to X1. And if you look at the equation you could 103 00:08:13,298 --> 00:08:19,255 see on the left you can have AN over that product and over on the right you can 104 00:08:19,255 --> 00:08:24,542 have AN minus one over that same product but the XN cancels, so its the product 105 00:08:24,542 --> 00:08:28,786 going up to N minus one. So again your first term on the right is 106 00:08:28,786 --> 00:08:33,850 equal to your first term on the left but with the N replaced by N minus one. 107 00:08:33,850 --> 00:08:36,810 So, let's take an example of how that works. 108 00:08:36,810 --> 00:08:41,973 Here is a more complicated recurrence. where we've got a factor that's a 109 00:08:41,973 --> 00:08:47,136 sequence, function of N that is multiplied by the AN minus one on the 110 00:08:47,136 --> 00:08:50,663 right. so the factor, what we're supposed to do 111 00:08:50,663 --> 00:08:56,310 is just take the product of. So this thing XN is, N plus one plus one 112 00:08:56,310 --> 00:08:58,264 over N. One plus one over N. 113 00:08:58,264 --> 00:09:03,332 and then we do XN minus one, so the same thing with an N minus one. 114 00:09:03,332 --> 00:09:08,690 Same with an N minus two all the way down to one, which is two time one. 115 00:09:08,690 --> 00:09:14,526 And if you look at this product in this case everything cancels, the N's cancel, 116 00:09:14,526 --> 00:09:19,794 N minus one cancels all the way down to the 2's cancel. So all is left is the N 117 00:09:19,794 --> 00:09:23,112 plus one. So that says the summation factor is N 118 00:09:23,112 --> 00:09:29,266 plus one or to solve this recurrence what we should do is, divide both sides by N 119 00:09:29,266 --> 00:09:32,775 plus one. So if we divide both sides by N1 plus one 120 00:09:32,775 --> 00:09:38,072 in this case, then we have AN over N1 plus one on the left, AN minus one over N 121 00:09:38,072 --> 00:09:40,091 on the right, and two over N plus one. 122 00:09:40,091 --> 00:09:45,103 as the term is added on. I presented this as magic in the 123 00:09:45,103 --> 00:09:50,406 quicksort lecture, but this is the same type of thing that we did for the 124 00:09:50,406 --> 00:09:54,619 quicksort lecture. This is to take a simple recurrence, and 125 00:09:54,619 --> 00:09:59,267 reduce it to one that telescopes by using a summation factor. 126 00:09:59,267 --> 00:10:03,117 And there's an easy formula for the summation factor. 127 00:10:03,117 --> 00:10:07,040 the cancellation maybe is magic, but not that magic. 128 00:10:07,040 --> 00:10:13,735 So now that thing telescopes and that again, each time it throws out a two over 129 00:10:13,735 --> 00:10:19,696 N plus one sets the sum of one over K plus one which K goes from a one to N 130 00:10:19,696 --> 00:10:27,126 multiplied by two so two then that's the harmonic numbers, and then just doing the 131 00:10:27,126 --> 00:10:33,361 algebra that's a solution. so now we've got a method for solving any 132 00:10:33,361 --> 00:10:38,920 recurrence of that form. we do get to a sum in, in these examples. 133 00:10:38,920 --> 00:10:45,545 They've been familiar sums but still that gives us a much broader class of 134 00:10:45,545 --> 00:10:51,789 recurrences than we know how to solve. We still need to be able to evaluate the 135 00:10:51,789 --> 00:10:55,363 sums. All right, so just an example and to 136 00:10:55,363 --> 00:11:00,898 check your understanding of this material, one thing you might do, is take 137 00:11:00,898 --> 00:11:04,801 a moment to verify the solution for that example. 138 00:11:04,801 --> 00:11:10,762 So that's the reccurence, and then what you want to do is plug in the solution 139 00:11:10,762 --> 00:11:14,097 given on the previous slide to see if it works. 140 00:11:14,097 --> 00:11:19,917 It just involves a little bit of algebra that you may not be familiar with, and 141 00:11:19,917 --> 00:11:25,239 but it's worthwhile to check your understanding of, of these definitions by 142 00:11:25,239 --> 00:11:31,670 doing that. [COUGH] So one thing that is good to do 143 00:11:31,670 --> 00:11:38,511 even before trying to do the algebra is to just do small values. 144 00:11:38,511 --> 00:11:42,162 so so that you know the small values, or as 145 00:11:42,162 --> 00:11:45,919 I mentioned, you could write a program to compute them. 146 00:11:45,919 --> 00:11:51,999 but if I've got a recurrence I can do the first value like As of one has gotta be 147 00:11:51,999 --> 00:11:56,849 two, and As of two has gotta be five, just by doing the really simple math 148 00:11:56,849 --> 00:12:00,742 there. and so over here in the solution that I'm 149 00:12:00,742 --> 00:12:05,452 supposed to have. I can check As of one it's supposed to be 150 00:12:05,452 --> 00:12:11,311 4H2 minus one and H2 minus one and H2 is one plus one-half minus one is just 151 00:12:11,311 --> 00:12:14,780 one-half times four is two so I've got it. 152 00:12:14,780 --> 00:12:20,216 in H3 minus one, that's one plus one half plus one third, subtract off the one, 153 00:12:20,216 --> 00:12:25,325 we're at one half plus one third, six times that is three plus two is five, got 154 00:12:25,325 --> 00:12:28,011 it. So once I've done that I have some 155 00:12:28,011 --> 00:12:33,251 confidence that I've got the solution and actually with only thing here, that 156 00:12:33,251 --> 00:12:38,884 almost that almost, that does result in a proof that I, you've got solution if your 157 00:12:38,884 --> 00:12:43,922 first few values are right. and but to really have a proof, what we 158 00:12:43,922 --> 00:12:50,304 want to do is plug in the supposed answer, AN minus one which would be 2N, H 159 00:12:50,304 --> 00:12:55,977 of N minus one over on the left, near the computation, see if you get AN. 160 00:12:55,977 --> 00:13:01,020 And that's the little bit of algebra that's required to do that. 161 00:13:01,020 --> 00:13:08,108 so have a solution always verify it in the computation with harmonic numbers 162 00:13:08,108 --> 00:13:14,812 involved realizing that H of N plus one equals H of N plus one over N plus one 163 00:13:14,812 --> 00:13:20,360 and that's where there is a little magic algebra in there to check that. 164 00:13:20,360 --> 00:13:26,397 all right, here's another exercise to test your understanding of the idea of 165 00:13:26,397 --> 00:13:32,359 solving a recurrence by multiplying by a summation factor and then telescoping. 166 00:13:32,359 --> 00:13:39,076 so this looks like a quite similar example and this is an exercise in the 167 00:13:39,076 --> 00:13:42,246 book. So you might take a moment to try to 168 00:13:42,246 --> 00:13:49,779 solve this problem. Well, if you've been paying attention to 169 00:13:49,779 --> 00:13:55,012 the lecture so far, you know that you want to do a, a semation factor, and the 170 00:13:55,012 --> 00:14:00,518 semation factor is somewhat similar to the one, that I did for the quick sort of 171 00:14:00,518 --> 00:14:04,800 like reccurence, comes out to be one over, N time N minus one. 172 00:14:04,800 --> 00:14:10,713 but actually in this case that's the hard way to solve this problem, I forgot the 173 00:14:10,713 --> 00:14:16,354 other thing that I said we should do when faced with a recurrence and that's to do 174 00:14:16,354 --> 00:14:20,500 the initial values. To do the initial values on this, so A1 175 00:14:20,500 --> 00:14:25,080 is one what's A2? Well 2A2 equals zero. 176 00:14:25,080 --> 00:14:32,700 so cancels out the A1 thing plus two. So two A2 is two, so A2 equals one. 177 00:14:32,700 --> 00:14:37,555 well, actually that is a proof if A2 equals one, then A3 is going to be, be 178 00:14:37,555 --> 00:14:40,885 equal to one, because just you know, rename N to get that. 179 00:14:40,885 --> 00:14:45,809 Actually, that's a proof that all the terms in this sequence are one. 180 00:14:45,809 --> 00:14:51,636 And if you try it with the summation factor you'll get to the same result but 181 00:14:51,636 --> 00:14:56,353 with a lot more algebra. This thing is just another way of saying 182 00:14:56,353 --> 00:15:01,138 that As of N equals one. so that's an example also you have to 183 00:15:01,138 --> 00:15:07,189 prove that, but again that's easy. so that's example or coverage of solving 184 00:15:07,189 --> 00:15:10,140 first-order occurrences by telescoping.