Tip:
Highlight text to annotate it
X
Next we'll, take a look at various different types of recurrences that are
more complicated than the linear first order that we just saw.
Just to get some idea of the types of things that, can arise when, we're, faced
with a recurrence relation, in general, to solve.
So, simp, simplest one we just looked at is a so called linear first order
recurrence. linear just means that we don't multiply
A sub N times A to the minus one or anything like that.
We just use [COUGH] coefficients that are not involving our unknowns.
and first order means that on the right hand side we just have one term a n - 1.
so here's non linear where we're dividing a n - one into a, into a constant so
that's not just a linear combination of it, it's dividing.
so that's first order nonlinear. And actually we'll talk about that one.
so here's second order linear. it's linear combination of AN - 1 AN - 2.
the coefficients can, can involve N's and consonants but not multiplying or
dividing with our unknowns. this is an example of a non linear second
order where it's a function of AN - one and AN - 2 but we can, we're multiplying
and taking square roots or whatever else. And these types of things can be very
easy to write down and they're even easier to write computer programs.
To compute values but doing the math Behind some of these can be quite a
challenge. so variable coefficients that's the, the
one that we started with where we don't use constants but we do use functions of
N the most 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 quicksort 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, 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. so what about non-linear first order
recurrences. Well, those are familiar actually, to
people who do numerical calculations and a very famous example of that is Newton's
method for computing roots of functions. and I'll just do an example for computing
the square root of two. Newton's method says to in order to
compute the square root of two what you do is start with some initial estimate
like start with two and then take the average of the your current value and two
over your current value. and use that as your next estimate.
That's defining a sequence. and you can see, from this formula, if
you're get close to the square root of two, or if you get exactly the square
root of two, two over the square root of two is square root of two, plus square
root of two, divided by two, is equal to square root of two, so you should
converge on the value of square root of two, that's Newton's method.
and I can write a code to compute the squared to two this way.
Just another sequence in the code that I gave for quick sort of Fibonacci numbers.
and if you print out values for that, you see it gets very close to the square root
of 2. actually very quickly.
and it's actually got quadratic convergence.
the number of significant digits doubles on each iteration.
It's a very efficient way to compute roots and applies to lots of other
functions not just square root. so that's non-linear first order
recurrence and again, doing the math to prove that this happens is you know,
certainly the analysis for algorithms, it's like analyzing this algorithm
but it's of a, 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 high order linear occurrences, those are something that, that come up a lot.
And, in the next lecture we are going to show a systematic solution that uses
generatic functions for solving recurrences like this, then actually
later on we're, we, we are going to examine it from an even more general
point of view. But, here's an example, so this is A.
Second order, linear recurrence with constant coefficient, kind of 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'd have a
lot of turns. 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
could be solved, and again, this is kind of a magic step but I'll show, next
lecture how this becomes systematic. this, say well, I think that it's going
to grow like a some number to the nth power.
So I'm going to say, let's say that A N equals X to the Nth.
So if an is going to be equal to x^n, then it would have to be the case that we
have x^n=5*x^n-1-6*x^n-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 by X to the N
minus two. So 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 two times X
minus three. and it means that,
both two to the n and three to the n are solutions to this and actually it's, it's
not too much of a step to see that the final solution must be of the form a sub
n equals some constant times three to the n plus some other constant times two to
the n. And again, I'm not going to go through
the proof of these postulations, cause 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 to 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 zero
which is a0 equal to c0 plus c1. And that, one which is a1 must be 3c0
plus 2c1. So those are simultaneous equations and
so c0 and c1 and then the solution is c0 = one, c1 = -1 and one + -1 is zero 3 * 1
+ 2 * -1 3 - 2 is 1 and then that's the solution.
A sub N = 3 to the n - 2 to the n is the solution to that equation.
and plug it in to check that, that's the answer.
but that definitely works in, 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 are the same setup. but, the, the coefficients are both one.
so then we get, actually a = x to the n. We get x to the n - 1 to the x-2, which
gives us this quadratic equation. x^22 -x0.
- 1 = 0. Solution to that using the quadratic
equation, -b + - square root of b^22-4ac, is going to have a square root of five in
it. b squared is one, 4ac is minus four minus
4ac is plus 4,1 plus four is five. and so it works out from the quadratic
equation that, that equation factors, in terms of those two roots.
One plus the square root of five over two, and one minus the square root of
five over two. in this one one plus the square root of
five over two is a very famous number known as the golden ratio.
and maybe we'll come back to that at some point.
It has all kinds of interesting properties.
but in the current context, it's just a root of that quadratic equation.
so again, just as before the solution must be linear combination of these two
terms. C0 times C to the N, plus, plus C1 times
V after the N. and how do we find out those
coefficients? same way.
we just plug in a zero equals zero. It has to be a, C1, zero plus C1, and A1
equals one, has to be fee C0 plus fee half C1.
Solve those two equations, and you find out that the, it's C0.
Is one over squared of five and C one is minus one over squared of five 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. 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, 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 in 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 and so that's an example.
nowadays where you use a symbolic math package to go ahead and compute the roots
and this is computing these with Sage but you can you, you use Mathematica or Maple
or other packages to go ahead and compute roots that's where you do it nowadays.
So we have an algorithm for solving [COUGH].
It's a higher order reoccurrences with constant coefficients, and we'll develop
this more fully, more fully, later on. the other point that I didn't mention is
the roots might be complex. and again, rather than go thru it in this
context we'll see what happens when we talk about in the context of generated
functions. Okay, the last thing, that I just want to
mention is that the a lot of times we get a recursive programs that map directly,
to, recurrences of the divide and conquer style and those are not traditionally
found in, studies of recurrence in, in mathematics.
That's something that's really brought to the table, by computer algorithms.
And we'll look at those, in some detail, later in this lecture.
That's the general. Types of reccurences that come up in the
analysis of algorithms.