1:45

So variable coefficients, that's the one that we started with,

Â where we don't use constants, but we do use functions of n.

Â And those arise a lot in the analysis of algorithms.

Â And then, there's higher order,

Â which go back way further than just the first two terms.

Â For example, the quick sort is an example of that, where it's a full history.

Â That is every value, every term in the sequence depends on

Â all the previous terms in the sequence.

Â That's a full history.

Â And then there's a special case that arises quite often in the analysis

Â of algorithms.

Â And that's the so called divide and conquer.

Â Where a sub n depends on terms say about halfway back in the sequence.

Â And, we'll have quite a bit to say about that in just a bit.

Â And those are very important in the analysis of algorithms.

Â 4:21

So that's non linear, first order recurrence.

Â And again, doing the math to prove that this happens

Â is certainly the analysis of algorithms.

Â It's like analysing this algorithm but

Â it's not of a nature, the recurrences of a quite different nature,

Â than the kind that we're going to largely be considering in this course.

Â So, higher-order linear recurrences, those are something that come up a lot.

Â In the next lecture, we're going to show a systematic solution that uses generating

Â functions for solving recurrences like this, and then actually later on we're

Â 5:02

going to examine them from an even more general point view, but here's an example.

Â So this is a second order of linear

Â occurrence with constant coefficients, like the Fibonacci numbers, and

Â so the idea is that it's hard to telescope this one.

Â You could try to telescope it, but very soon you have a lot of terms and

Â maybe not so much of an idea of where it's going to go so easily.

Â So one way to see how such an equation can be solved and again

Â this kind of a magic step, but I'll show next lecture how this becomes systematic.

Â Is to say well, I think that it's going to grow like some number to the Nth power.

Â So lets say that A N equals X to the N.

Â So if A N is going to be equal to X to the N, then it would have to be the case that

Â we have X to the N equals 5 X to the N minus 1 minus 6 X to the N minus 2.

Â In that kind of equation is a good thing for us,

Â because it means we can get rid of the N by just dividing X to the N minus 2.

Â For now we've just got a quadratic equation, and

Â we've known since middle school how to solve quadratic equations.

Â So that factors to x minus 2 times x minus 3.

Â And it means that both 2 to the n and

Â 3 to the n are solutions to this, and actually

Â it's not too much of a step to see that the final solution must be of the form ace

Â of n equals some constant times 3 to the n plus some other constant times 2 to the n.

Â And again, I'm not going to go through the proof of these postulations,

Â because I'll give a very systematic way for doing it in just the next lecture.

Â But you can believe from these manipulations that that's what's gotta

Â happen, and so now what we have to do is find those two constants.

Â Well those two constants are easy to find, because the initial conditions.

Â We have two constants that we need, and

Â we have two initial conditions so we can just plug in for A0 and A1.

Â And it says that we must have that 0, which is A0, is equal to C0 plus C1.

Â And that one, which is A1 must be 3Z0 plus 2C1.

Â So those are simultaneously equations in c 0 and c 0, and

Â then the solution is c 0 equals 1 c 1 equals minus 1, 1 plus minus 1 is 0.

Â Three times 1 plus 2 times minus 1,

Â 2 minus 2 is a 1 and then that's the solution.

Â Plus 3 to N minus 2 to the N is the solution to that equation,

Â and plug it in to check that's the answer, but

Â that definitely works in this case.

Â And that kind of technique is going to work for any second order

Â linear recurrence with constant coefficients, like the Fibonacci numbers.

Â Fibonacci numbers, the same setup, but the coefficients are both 1,

Â so then, we get xn = xn-1 = xn-2,

Â which gives us this quadratic equation, x2-x-1=0.

Â Solution to that, using the quadratic equation,

Â minus b plus/minus the square root of b squared minus 4 ac,

Â is going to have a square root of 5 in it, B squared is 1.

Â 4 ac is minus 4.

Â Minus 4 ac is plus 4.

Â 1 plus 4 is 5.

Â And so it works out from the quadratic equation.

Â That equation factors in terms of those two roots.

Â 1 + the square root of 5 over 2, and 1- the square root of 5 over 2.

Â In this one, 1 + the square root of 5 over 2.

Â It's a very famous number known as the golden ration,

Â and maybe we'll come back to that at some time.

Â It has all kinds of interesting properties.

Â But in the current context, this just a root of that quadratic equation.

Â 9:29

So, again, just as before, the solution must be linear

Â combination of these two terms c0 times c to

Â the n plus c1 times theta to the n, and how do we find those coefficients?

Â Same way we just plug in a zero equals zero has to be c0 plus c1,

Â and A1 want to equal one has to be phi c0 plus phi hat c1,

Â solve those two equations, and you find out that the c0,

Â is 1 over square root of 5, and c1 is minus 1 over square root of 5.

Â And that's a solution.

Â So that's what we're after, is given the recurrence,

Â we have a simple equation for the nth term.

Â That's solving the recurrence.

Â 10:19

And again, we can do that systematically for any such recurrence.

Â And this will come up, another couple of times, in the next few lectures.

Â So, this procedure, in a sense, it amounts to an algorithm.

Â So that is given any recurrence that we can go through this and

Â come up with a solution and that's ideal.

Â Actually there's one case that we didn't consider, and

Â that is what if the roots are the same.

Â If the roots are the same, then we get an N times the root to the Nth term there.

Â And that's discussed in the text.

Â But I'm not going to talk about it now because,

Â again, we're going to do this with generating functions next time.

Â So what you wind up is needing to compute roots of equations quickly.

Â And this extends to higher order recurrences.

Â So that's the an example,

Â now a days where you use a symbolic math package to go ahead and compute the roots.

Â And this is computing things with sage, but you can

Â 11:53

The other point that I didn't mention is the roots might be complex.

Â And again, rather than go through it in this context, we'll see what happens

Â when we talk about it in the contents of generating functions.

Â Okay, the last thing that I just want to mention is that the,

Â a lot of times we get recursive programs that map directly to

Â recurrences of the divide and conquer style, and

Â those are not traditionally found in studies of recurrence in Mathematics,

Â that's something that's really brought to the table by computer algorithms.

Â We'll look at those in some detail later in this lecture.

Â That's the general types of recurrences that come up in the analysis of

Â algorithms.

Â