So, but, now we're going to talk about Singularity Analysis.

Now, just a quick review of one of the keys to singularity analysis is our

ability to use the Taylor theorem to approximate functions at points that

aren't singular. That's a definition of an analytic

function is it's differentiable everywhere if it's analytic at a point,

it's differential everywhere at the point.

and that means you can expand it at the point just using Taylor's theorem.

So say if we have this function that I show before e to the minus z squared over

2 minus z squared over 4. And we want to expand it at z equals 1.

then we can just go ahead and compute the derivatives and evaluate them at 1.

So f of the function evaluated at 1 is e to the minus three quarters.

the derivative evaluated at 1 is plus e to the minus three quarters because 1

plus 1 is two, and then there's a minus that cancels out.

the second derivative evaluated at 1 you can get either minus three quarters over

4 and so forth. And just use Taylor's Theorem to develop

an expansion of the function at any point that it's not singular.

and that's a fine method that's been known for centuries and that's.

what we're going to do for singularity analysis is to exploit this ability to

approximate functions at non-singular points in terms of a po-, a power series

and that's what's going to take us to the standard scale as, as we'll see.

now nowadays we know people don't compute derivatives so much by hand anymore.

you can just use a computer and for a symbolic package and so this is Wolfram

Alpha, type in so say I want to know the series representation of square root of 1

minus 1 plus z over 2z at z equals one third.

I can just put it in that function at z equals one third and how many terms I

want and it'll tell me exactly the expansion.

So I don't have to compute that by hand. So people don't compute those things by

hand so much anymore. if you need to do it figure out how to

get a computer to do it, it's a much faster way to proceed.

actually, we're going to use these kinds of approximations in this lecture, only

early on to demonstrate the method. In practice, a great many of the

applications of singularity analysis are based on general schema, where we don't

have to do the expansion. it's all hidden underneath the covers in

terms of general schema. but still it's important to remind

ourselves what it's all based on. And Taylor theorem is definitely it.

okay, so here's an overview of the general approach to coefficient

asymptotics, for non-member functions. So again always we gotta locate the

singularities; in particular, we gotta find the one closest to the origin.

and that's what's going to give the exponential growth factor.

that's no different even when there's essential singularities.

There's one of them that's closest to the origin.

So, just running example, we'll use unary binary trees, so that's trees where all

nodes have degrees zero, one, or two. we develop this generating function for

it using the symbolic method. closest uh, [COUGH] singularity of the

origin is z equals one third. There's another one further out at minus

1, but that, that's the one that matters. So the exponential growth factor is

going to be 1 over that, which is 3 to the n.

so, that's the first thing. so then the next thing is to figure out

where the function is analytic near the dominant singularity, basically, where's

that slit? And then we're going to use functions

from the standard functions scale to approximated, near that dominant

singularity using Taylor theorem and we approximations that extend, in principal.

so, uh, [COUGH] we'll look at how to develop for, for this function an

approximation like this. and we can, can, carry it out like this.

as many terms, as we wanted. so that's, first key is, we have to know

where it's analytic. and, well we'll see how that comes out in

the proof. and then, the, the other basic idea in

singularity analysis is, Now we've got the thing expressed as

approximation using the standard scale. we can do term by term transfer and

immediately transfer this using the standard scale to the result.

And even transfer the big O to the corresponding result.

that's another key to the method, is term-by-term transfer is valid.

That has to be proved and that's one of the keys to the method.

and as I said, in the overview lectures, this paper was a real watershed in

analytic cognitorics. before that, people knew things kind of

like this. But after that, this is the scientific

basis for we can mathematically prove that we can do these kinds of

manipulations. and that's what led to the devlopment of

general schema and many other things that we won't have time to get to in this

course. So the whole idea of singularity analysis

depends on the function being analytic, in a region near its singularities.

in, so again for square root and log, usually talking about a slit and the key

idea is a thing called a delta domain. And they call it a delta analytic

function so that's one that's analytic in this particular shape where we take the

slit and we carve out a little v near the slit and then the other way other wise

it's a circle. so it's, it's a little bit weaker than

what the Hankle contour had which was a little circle cut out here and but that

that little difference makes a huge difference in allowing the transfers of,

of the type that we're going to consider. it may not not, people may not be able to

understand these kind of distinctions without really studying this derivation

in the book. but these, these distinctions are there.