Today we're going to talk about generating functions. As you'll see, generating functions are the central object of study in Analytic combinatorics. But they also have rich history and many uses and we'll show first how they are used for solving recurrence relations, and then ease into their use in more general context. So, to start off, we're going to talk about just what is a generating function. In this, the fist thing we'll talk about is what is called ordinary generating functions. So, there's a definition of what is ordinary generating function? it's a function that's defined as an infinite sum, involving a free variable, Z in this case over a sequence. So given a sequence A0, A1, infinite sequence like the types we were working with recurrences the ordinary generating function of that sequence is obtained by multiplying the Kth term by Z to the K and then summing over old K. We also use the notation that inside brackets Z to the N of A of Z, is the coefficient of Z to the N in A of Z. and a lot of times we want to refer to what the coefficient is. and we'll see how it, it applies, but let's just talk formally about some examples of generating functions first. So for example, if the sequence is all ones, then the generating function for that sequence is the sum N greater to 0 Z to the N, which is geometric sum 1 / 1 - Z. or if you have one 1/2. 1/6. 1/24, the sequence is one over n factorial. The generating function of that sequence is sum n bigger than zero, z to the n over n factorial, that's e to the z. So that's examples of generating functions. And we'd say the coefficient of Z to the N and E to the Z is one over N factorial. so that's ordinary generating functions. now the significance of defining a generating function is that it allows us to represent an entire infinite sequence with a single function. rather than carrying around the infinite sequence, 1/n factorial, we just work with the single function, e of z. And that turns out to have all kinds of benefits when we're doing analysis of algorithms, and studying properties of combinatorial structures. But before getting into the applications, let's look again at some more basic operations on generating functions that we'll use in order to be able to, we need to be able to find the generating function of a given sequence. And we need to be able to see the sequence back, given the generating function. Then we use some relatively simple operations to get these jobs done. So for example, here's the scaling operation. If you have a of z, tis is just generating function for some sequence, if you multiply the argument by a constant c. So, just evaluate a of CZ then just do the math. That's the sum of c, c to the k, z to the k. That's the generating function of the sequence a0, ca1, c^2 a2, c^3 a3, and so forth. and that's just, from, from the math. CKZK is the Is the generated function of that sequence. So here for example, if you have the sequence that's all ones, where it's, ogf1 over one minus z. then one over one minus 2z is the sum of two to the n, z to the n, which is the generating function for the powers of twos. So that's scaling. So that's an easy way to get generating functions for different sequences out of a known sequence. and again, we'd say coefficient of z to the n and 1over one minus 2z is two to the n. So that's scaling. let's look at another example, addition. That's an easy operation in generating functions. If you have two generating functions on two different sequence, then the sum of the generating functions is the the OGF of the term by term sum of the sequences. So, for example, these two generating functions that we've developed here if we subtract the say we subtract the first one from the second, 1u200bz-u200b1/u200b1-u200bz over, 1 - 2Z - 1 / 1 - Z that's the generating function for powers of 2-1. so with each one of these operations we enrich the set of sequences that we know generating functions for. differentiation that's another thing, if we have a generating function A of Z = A K Z to the K, if we differentiate that. That's Z a prime of Z. This KAKZ to the K. that's the generating function of this sequence A1, 2A2, 3A3, and so forth. so, then that's a useful operation, that we can use again to get, generate functions for more sequences. So for example with our simple geometric sum for the sequence that's all 1s and differentiate that. Differentiate the left side it's Z over one minus Z squared. and the right side tells us that's the generating function for the natural numbers. Sequence 0, 1, 2, 3, 4, 5. We can do that again, we can continue differentiating and get a richer set of functions. So differentiate again, it's Z squared over one minus ZQ. and that's the generating function for the binomial coefficients, N choos 2 [COUGH], or N times N - 1 / 2. and actually we can get a generating function for binomial coefficients on the lower index, by differentiating, N times, in this way, and you can, check that out. The generating function for N choose M, is Z to the M, over one minus Z to the M plus one. and as we saw special number sequences like the binomial coefficients arise when we're studying algorithms and combinatorial structures. so with generating functions we can work with all these kinds of sequences with just one function. so [COUGH] oh, and this is just dividing by, dividing out z to the n, we get a slightly different look at that same generating function. and we'll have use for applying all of these equations which are in tables in the book later on. okay, we can go the other way and we can integrate. if you have a OGF if you integrate it from zero to Z. if you do it term by term the definition, you see that, that gives us the OGF of the sequence, A1 over two, A2 over three and so forth. so, taking our standard integrating it. On the left, it's natural log of one over one minus Z. On the right, it's the sum Z to the N over N or the generating function for the sequence, one, one half, one third, one fourth, and so forth. [COUGH] so that's integration. and we can, actually, integrate more and get more, answers, but, let's look at another thing, In that is, partial sum, if you have a genarating function and you multiply by one minus Z, then you get the generating function of the partial sums of the sequence. so the original sequence is A0, A1, and so for, partial sums there A0, plus A1, A0 plus A1, plus A2 and so forth. Let's look at a proof of that fact so that's just running down the definition of the two sequences 1 1 1 - z is some big until zk and AFC is by definition some ingredients of a and zn so we have the product of those two sums. so we distribute to bring in the powers of z together and give us that double sum. then the next thing is to, in the inner sum, change N to N minus K. and so then we have A, N minus K and Z to the N so, there's only, N in the exponent of Z, and then switch order of summation, so K be going in your little zero, N bigger than or equal to K, if we switch order of co, summation that's the same as N bigger than zero, the K restricted to between, be between zero and N. and then, in that inner sum, we can change, k to n - k. and then we see that we have the partial sums. So the generating function. so this product is the generating function of that sequence which is the partial sums. so, that's another, fine operation, to be able to perform to give us a richer set of functions, of sequences that we now generating functions for. So for example if given our two of the generating functions that we've already derive two of the sequences that we've already derived generating functions for. If we multiply those together. Or one over one minus Z times, log one minus Z, we get the generating function for the harmonic numbers, a harmonic numbers is sum from, of K goes from one to N of one over one mine, one over K. and we saw that the harmonic numbers, arose in the analysis of quick sort and naturally arise in many places in the analysis of algorithms and now we have, we can represent'em with that single function, one over one minus Z, natural log of, one over one minus Z. and that partial sum idea, generalizes to the idea of a convolution. if you have, any two generating functions, you can multiply them together. and you get the, generating function for this, convolved product. sum from where the nth term in the sequence is sum from zero goes from k to n of akbn-k. And here's the proof of that. It's just pretty much the same as the proof that we just did for partial sums where we distribute then we change in the inner sum. We change n to n - k [COUGH] and then we switch order of summation and that gives us the convolved product. So that's convolution. so for example, if, another way to derive the generating function for the natural numbers, is just to, square the generating function for ones, and then that, you know you can do the math to see that this convolved product is just N plus one in that case. And that's a different way to derive the generating function for the natural numbers. So that's convolution. So the summary is that we can, what's called, expanding a generating function by, the. expressing an unknown generating function as a power series. That's finding the coefficients. in, you can look at what we've been doing as both directions given a sequence what's the generating function or given a generating function what's the sequence. So let's look at the first one given a, second one given a generating function what's the sequence what we've really been using is Taylor's theorem. That if you can differentiate the function then you can expand it and know the coefficients of Z to the N, it's just the Nth derivative of the function divided by N factorial. That's really what's behind the series that I gave for E to the Z, Z to the N over N factorial. or for one over one minus Z, the geometric series. the derivatives give factorials and they cancel out and you get one. So you can get your basic starting point from the Taylor Theorem usually and that's. that's what I just mentioned. But also, you can reduce to known generating functions. as we did for example. if we have 1 / 1 - z. Natural log of 1 / 1 - z. We know how to find the coefficients of z to the n in that. by, the process of convolution. so that's a summary of what we do to find coefficients given a generating function. And so the other way, if we're given this sequence. how do we find the generating functions? The same is just the same thought, just worked the other way. we integrate 1 / 1 - z, to get the generating function for one over k, and then convolve it with 1- z. to get our generating function. So that's, working with generating functions, just using the basic operations, that we've talked about. So here's a exercise that now you should think about to cement your understanding of the idea of ordinarity generating functions and the sequences that [COUGH] the sequences that they represent. So let's prove that using generating functions, prove that the sum of the harmonic numbers from K goes from 1 to N has this value. remember when we talked about solving recurrences we said that we're going to find that we need, we're going to have sums that we need to evaluate and how are we going to evaluate a sum like that if it's going to turn up, and generating functions are a reasonable tool for doing something like this. So think about if you, if you can solve that problem to apply your understanding of the last couple of slides in the lecture. So what we do is for the left-hand side, so what's the generating function for the left-hand side? Well we know the generating function for the harmonic numbers, that's one over one minus Z, log of one over one minus Z. If we multiply that by one minus Z, then we get the generating function for the sum. So first thing, that gives us the generating function for the left-hand side. So now to what we want to do is we want to extract coefficients from that generating function in a different way. And what we'll do is we'll. convolve natural log of 1-z with 1 / 1 - z^2 to get the coefficients. So that tells us right away that the coefficient of z to the n in this its a convolution, its a summon k the coefficient of z to the n in that one will n - it and the coefficients z the n and that one over k. So, that's just a convolution of, simple convolution of those two generating functions. It's a sum, but it's, all the pieces of that sum we can do. we just have to do a little bit of math. It's N plus one, times H of N, that's the first term. And then, minus K over K, and there's N terms, it's just minus N. And then, just need to note that H of N is H of N plus one, minus one over N plus one. And then, a little algebra gives us the solution. So that's an introduction to ordinary generating functions and some calculations that gives us the useful ways to work with sequences and evaluate sums and do other operations just because of the idea that we can represent an entire sequence with the single mathematical function.
