0:04

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.

Â 3:09

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.

Â 8:48

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.

Â 10:07

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.

Â 11:16

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.

Â 13:45

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.

Â