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.