Now we're going to talk about telescoping and recurrence. That's a basic technique for solving recurrences, so let's get into general techniques for solving a recurrence. So this type of recurrence is called a linear first order recurrence. So that means that [COUGH] the coefficients are constant and there's only one term on the right hand side. So this is a very simple recurrence. And what I want to show with this example is that recurrence like this always telescope to a simple sum. So what we do is, take the same equation for n-1 and apply it. So apply the same equation for n-1, and we did this in the middle of a quick sort of an example before. So if an = an-1+n then an-2 + (n-1) and the thing is we can do the same thing just do it again, an-2 has got to equal an-3 + n-2. And the idea is to keep doing that, that's called telescoping, until we get down to a0. So when we have a0 here then we are left with a2, or we just threw out a1 every time we throw out a thing that's equal to the ones on the left. So that's a proof that a sub n is equal to a0 plus the sum from 1 goes from k to n of k. That's a solution to the recurrence. Well maybe it's not that helpful a recurrence because we have to know how to evaluate the sum. In this case, the value of the sum is half n+1 times n. But in general, we might have a more complicated bit of mathematics to do. And however you evaluate the sum, it's easy to check that it's a solution to the recurrence. N+1 times n over 2 is equal to n times n-1 over 2 + n. We put in a 2n over 2 and just add in the minus 1 becomes a plus 1. So that's a quick solution, and what it says is that if we have a first order linear recurrence, that's equivalent to being able to evaluate a sum. Now the challenge is how we're going to evaluate sums. And there's some elementary discrete sums that turn up, that we have to be able to do. And many of these are familiar, so anyway we'll catalog them. And in the book, there's discussion of how we know these things to be true, but many of these are familiar. So that's the standard sum of a geometric series. Sum k goes from 0 less n of x to the k is 1-x to the n over 1-x. And similarly arithmetic series, that's the one we just did. That's another way to write that value. I now use less than so less than equal, so it's n times n-1 over 2. And that's the binomial coefficient, n choose 2. And that's actually can be generalized to a sum. This is the case m = 0, and if we generalize that to any value of m, that's a sum of a binomial in the upper coefficient. Is n + 1, choose n + 1. [COUGH] The binomial theorem is like summing on the lower index binomial coefficient. And then that's what x + y to the n is equal to. So that's another sum that comes up. Here's one that turned up for quicksort, that's the harmonic numbers. The sum of 1 over k from k goes from 1 to n is defined to be the harmonic number, H sub n. And that's a discrete sum that comes up very often in the analysis of algorithms. And then there is more complicated ones that involve more complicated sum end. So this one is called the Vandermonde convolution, when you have two binomial coefficients n choose k and m choose t-k. Sum down the lower, if you sum those, you just add across and get m + some m choose t. So those are examples of elementary discrete sums. And maybe people are familiar with these from some math course or another. And we talk about how some of them in the book. But really, if you want to learn about how to do discrete sums, see Knuth volume I or the Knuth Graham Patashnick book that's referenced in the text. So from this point on, I'm going to kind of assume at least these and maybe some others that can be easily derived from elementary analysis. So but still that is not a very rich class of recurrences that we talked about how to solving with the [COUGH] linear first order recurrence, because the coefficient of an-1 was 1. So first example where it gives us a richer class of recurrences when this coefficient is not 1. So here's a simple example, a sub n = 2 a sub n-1 + 2 to the n. Again with a 0 = 0, we always have to specify everything. That should be for n greater than 0, with a0 = 0. So that doesn't immediately telescope, we could apply the same equation for an-1, but then we have to take care of the 2 and we get 2 complicated nested parentheses. To avoid that in this case, what we do is just divide by 2 to the n. If we divide every term in this equation by 2 the the n, then the 2 to the n becomes 1. And then we do get an equation at telescopes, because the first term on the right hand side is the same as the first term in the left hand side except within replaced by n-1. So now we can go ahead and telescope this thing and in this case, every time we go down, one throws out a 1 and so we get down to a0 after n times. So that's a proof by telescoping that a sub n over 2 to the n is equal to n. And then just multiply it by 2 to the n and that's a proof that a sub n equals n2 to the n. So that's a solution by using a summation factor to turn a linear first order recurrence into one that telescopes. And again you can check by, if you don't believe the solution. N should always do this even if you do believe it is check that it works. So if we put n2 to the n and 2 (n- 1) 2 to the n-1 + 2 to the n then do the math. That's 2 times 2n that's 1 that's n2 to the n and then we have a -2 to the n + 2 to the n so that checks. So that's a solution to a recurrence with a constant first coefficient, but now the challenge is how do we find the summation factor. It turns out to be not too difficult. Actually, there's two different ways, but the main one that we're going to use is shown right here. And it works even when the coefficient is not a constant, but some sequence. All we do is divide both sides by the product, Xn, Xn-1, Xn-2 down to X1. And if you look at the equation, you can see on the left you can have an over that product. And over on the right you can have an-1 over that same product that the Xn cancels. So it's a product going up to n-1. So again, you first term on the right is equal to your first term on the left, but with n replaced by n-1. So let's take an example of how that works. Here's a more complicated recurrence where we've got a factor that's a sequence function of n that is multiplied by the n-1 on the right. So the factor, what we're supposed to do, is just take the product. So this thing, xn is n + 1 over n 1 + 1 over n, then we do Xn-1, so the same thing with a n-1, the same thing with a n-2 all the way down to 1, which is 2 times 1. And if you look at this product in this case, everything cancels. The n's cancel, n-1 cancels, all the way down to the 2's cancel. So all that's left is the n+1. So that says the summation factor is n+1 or to solve this recurrence, what we should do is divide both sides by n + 1. So if we divide both sides by n + 1 in this case, then we have an over n + 1 on the left, an-1 over n on the right, and 2 over n + 1 as the term, is added on. I presented this as magic in the quick sort lecture. This is the same type of thing that we did for the quick sort lecture. We take a simple recurrence and reduce it to one that telescopes by using a summation factor. And there's an easy formula for the summation factor. The cancellation maybe is magic, but not that magic. So now that thing telescopes and that again, each time it throws out a 2 over n + 1, sets the sum of 1 over k + 1, as k goes from 1 to n multiplied by 2. So 2, and that's the harmonic numbers, and then just doing the algebra that's a solution. So now we've got a method for solving any recurrence of that form. We do get to a sum, in these examples they've been familiar sums. But still that gives us a much broader class of recurrences that we know how to solve, still need to be able to evaluate the sums. So just as an example and to check your understanding of this material. One thing you might do is take a moment to verify the solution for that example. So that's the recurrence, and then what you want to do is plug in the solution given on the previous slide to see if it works. It just involves a little bit of algebra that you may not be familiar with, but it may be worth your while to check your understanding of these definitions by doing that. [COUGH] So one thing that is good to do even before trying to do the algebra is to just do small values. So that you know the small values or as I mentioned you can write a program to compute them. But if I've got a recurrence, I can do the first value like a sub 1 has got to be 2, and a sub 2 has got to be 5, just by doing the really simple math there. And so over here, in the solution that it's supposed to have, I can check a sub 1, supposed to be 4 h2-1 and h2-1, h2 is 1 + 1/2-1 is just 1/2 times 4 is 2, so I've got it. And h3-1, that's 1 + 1/2 plus 1/3, subtract off the 1 we got 1/2 + 1/3, 6 times that is 3 + 2 is 5, got it. So once I have done that I have some confidence that I have got the solution. And actually with only one thing here that almost, that does result in a proof that you've got the solution if your first few values are right. But to really have a proof what we want to do is plug in the supposed answer an-1 which will be 2n, H of n-1 over on the left. Do the computation and I'll see if you get an. That's the little bit of algebra that's required to do that. So have a solution, always verify it. And the computation with harmonic numbers involves realizing that each event plus one equals H of n + 1 over n + 1. And that's where this little magic algebraic in there to check that. Here's another exercise to test your understanding of the idea of solving a recurrence by multiplying by a summation factor and then telescoping. So this looks like quite similar example and this is an exercise in the book. So you might take a moment to try to solve this problem. Well if you've been paying attention to the lecture so far you know that you want to do a summation factor. And the summation factor is somewhat similar to the one that I did for the quick sort like recurrence. Comes out to be 1 over n time n-1. But actually in this case, that's the hard way to solve this problem. You forgot the other thing that I said we should do when faced with a recurrence, and that's to do the initial values. If you do the initial values on this, so a1 is 1, what's a2? Well a2, 2a2 equals 0, so it cancels out the a1 thing + 2, so 2a2 is 2, so a2=1. Well actually that is a proof, if a2 = 1 then a3 is going to be equal to 1 because just rename n to get that. Actually that's a proof that all the terms in this sequence are 1. And if you try it with the summation factor you'll get the same result, but with a lot more algebra. This thing is just another way of saying that. a sub n = 1, so that's an example. So you have to prove that but again, that's easy. So that's example of coverage for solving for server occurrences by telescoping.
