Okay, now we're going to talk about. 
Telescoping a 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 there's 
[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 recurrences like this always 
telescope to a simple sum. 
so what we do is, take the same equation 
for N minus one and apply it. 
So applied the same equation for N minues 
one. 
And, we did this in the middle of the 
quick service example before. 
So, if AN equals AN minus one plus N, 
then AN minus one equals N minus two plus 
N minus one. 
And the thing is we can do the same 
thing. 
We just do it again. 
AN minus two has got to equal N minus 
three plus N minus two. 
And the idea is to keep doing that and it 
is called telescoping until we get down 
to 80. 
so, 
when we have ao here, then we're left 
with A1. 
or we just threw out a one. 
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, sum from one goes from K to N 
of K. 
that's the 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 plus one 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 plus one times N over two is 
equals to N times N minus one over two 
plus N. we put in a 
2N over two and just add N the minus one 
becomes a plus one. 
So that's a a quick solution and now what 
it says is, that if we have a first order 
linear recurrence we can, 
that's equivalent to being able to 
evaluate a sum. 
now the challenge is how are we going to 
evaluate sums? 
and there's some elementary discrete sums 
that turn up that we have to be able to 
do. 
And, and many of these, are familiar 
So anyway, we'll catalog'em. 
and in the book there's a discussion of 
of, 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 zero less than N of X to 
the K, 
is one minus X to the N over one ninus X. 
and similarly arithmetic series that's 
the one that we just did. 
that's another way to write that u, 
value. 
now we use less than instead of less than 
or equal so it's N times N minus one over 
two and that's the binomial coefficient N 
choose two. 
and that's actually can be generalized to 
do a sum this is the case, M equals zero. 
and if we generalize that to any value of 
M that's the sum of a binomial on the on 
the upper coefficient is M plus one 
choose M plus one. 
[COUGH] the binomial theorem is like 
summing on the lower index binomial 
coefficient. 
and then you can X, that's what X plus Y 
to the N is equal to. 
so that's another sum that comes up. 
here's one that turned up for quick sort, 
that's the harmonic numbers, the sum of 
one over K. 
from K goes from one to N is defined to 
be the harmonic number H of N. 
in that's a discreet sum that comes up 
very often in the analyses of algorithms. 
and then, there's more complicated ones 
that involve more complicated sumons, 
sumans. 
So, this one's called a vandermon 
convolution. 
When you have two binomial coefficients N 
choose K and M choose T minus K, summed 
on the lower. 
if you sum those you just add across and 
get M plus sum N 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 some of them in in the 
book. 
But really, if you want to learn about 
how to do discrete sums. 
see [INAUDIBLE] volume one or the 
[INAUDIBLE] book that's referenced in the 
text. 
So from, from this point on I'm going to 
kind of assume at least these and maybe 
some of some others that can easily be 
derived from elementary analysis. 
okay 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 minus one 
was one. 
And so, first example where it gives us a 
richer class of recurrences is when this 
coefficient is not one. 
so here is a simple example, A sub N 
equals two, A sub N minus one plus two to 
the N. 
Again, with a zero equals zero we always 
have to specify everything that should be 
for n greater than zero where a zero 
equals zero. 
so that, 
doesn't immediately telescope. 
We could apply the same equation for AN 
minus one but then we have to take care 
of the two and we get two complicated 
nested parentheses. 
To avoid that in this case what we do is 
just divide by two to the N. 
If we divide every term in this equation 
by two to the N, then the two to the N 
becomes one. 
and then we do get an equation that 
telescopes. 
Because the first term on the right hand 
side is the same as the first term on the 
left hand side, except with N replaced by 
N minus one. 
So now we can go ahead and telescope this 
thing. 
And in this case every time we go down 
one, it throws out a one. 
and so, we get down to A0 after N times. 
so that's a proof by telescoping that A 
sub N over two to the N is equals to N. 
and then just multiply by two to the N, 
and that's a proof that A sub N equals N, 
two to the N. 
So that's a, a solution by using a 
summation factor to turn a, linear first 
order recurrence into one that 
telescopes. 
and then again, 
you can check by if you don't believe the 
solution. 
And you should always do this even if you 
do believe it, is check that it works. 
so if we put N two to the N and 2N minus 
two to the N minus one plus 2 to the N do 
the math. 
that's two times 2N, that's one, that's 
N2 to the N. 
And then we have a minus 2N plus 2N. 
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. 
It works even when the coefficient is not 
a constant but some sequence. 
All we do is divide both side by the 
product XN, XN minus one, XN minus two 
down to X1. 
And if you look at the equation you could 
see on the left you can have AN over that 
product and over on the right you can 
have AN minus one over that same product 
but the XN cancels, so its the product 
going up to N minus one. 
So again your first term on the right is 
equal to your first term on the left but 
with the N replaced by N minus one. 
So, let's take an example of how that 
works. 
Here is a more complicated recurrence. 
where we've got a factor that's a 
sequence, function of N that is 
multiplied by the AN minus one on the 
right. 
so the factor, what we're supposed to do 
is just take the product of. 
So this thing XN is, N plus one plus one 
over N. 
One plus one over N. 
and then we do XN minus one, so the same 
thing with an N minus one. 
Same with an N minus two all the way down 
to one, which is two time one. 
And if you look at this product in this 
case everything cancels, the N's cancel, 
N minus one cancels all the way down to 
the 2's cancel. So all is left is the N 
plus one. 
So that says the summation factor is N 
plus one or to solve this recurrence what 
we should do is, divide both sides by N 
plus one. 
So if we divide both sides by N1 plus one 
in this case, then we have AN over N1 
plus one on the left, AN minus one over N 
on the right, 
and two over N plus one. 
as the term is added on. 
I presented this as magic in the 
quicksort lecture, but this is the same 
type of thing that we did for the 
quicksort lecture. 
This is to 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 two over 
N plus one sets the sum of one over K 
plus one which K goes from a one to N 
multiplied by two so two then 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, in these examples. 
They've been familiar sums but still that 
gives us a much broader class of 
recurrences than we know how to solve. 
We still need to be able to evaluate the 
sums. 
All right, so just 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 reccurence, 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, and 
but it's worthwhile to check your 
understanding of, 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 
so that you know the small values, or as 
I mentioned, you could write a program to 
compute them. 
but if I've got a recurrence I can do the 
first value like As of one has gotta be 
two, and As of two has gotta be five, 
just by doing the really simple math 
there. 
and so over here in the solution that I'm 
supposed to have. 
I can check As of one it's supposed to be 
4H2 minus one and H2 minus one and H2 is 
one plus one-half minus one is just 
one-half times four is two so I've got 
it. 
in H3 minus one, that's one plus one half 
plus one third, subtract off the one, 
we're at one half plus one third, six 
times that is three plus two is five, got 
it. 
So once I've done that I have some 
confidence that I've got the solution and 
actually with only thing here, that 
almost that almost, that does result in a 
proof that I, you've got solution if your 
first few values are right. 
and but to really have a proof, what we 
want to do is plug in the supposed 
answer, AN minus one which would be 2N, H 
of N minus one over on the left, near the 
computation, see if you get AN. 
And that's the little bit of algebra 
that's required to do that. 
so have a solution always verify it in 
the computation with harmonic numbers 
involved realizing that H of N plus one 
equals H of N plus one over N plus one 
and that's where there is a little magic 
algebra in there to check that. 
all right, 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 a 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, a semation factor, and the 
semation factor is somewhat similar to 
the one, that I did for the quick sort of 
like reccurence, comes out to be one 
over, N time N minus one. 
but actually in this case that's the hard 
way to solve this problem, I forgot the 
other thing that I said we should do when 
faced with a recurrence and that's to do 
the initial values. 
To do the initial values on this, so A1 
is one what's A2? 
Well 2A2 equals zero. 
so cancels out the A1 thing plus two. 
So two A2 is two, so A2 equals one. 
well, actually that is a proof if A2 
equals one, then A3 is going to be, be 
equal to one, because just you know, 
rename N to get that. 
Actually, that's a proof that all the 
terms in this sequence are one. 
And if you try it with the summation 
factor you'll get to the same result but 
with a lot more algebra. 
This thing is just another way of saying 
that As of N equals one. 
so that's an example also you have to 
prove that, but again that's easy. 
so that's example or coverage of solving 
first-order occurrences by telescoping.