Generating Functions and Combinatorial Identities

okay in this video we're gonna look at a tool for manipulating generating functions to come up with new combinatorial identities so let's just recall that given a sequence of numbers a 1 a 2 up to infinity its generating function is given by a of X which is the sum N equals 0 to infinity a and X to the N so in other words the coefficients of this power series are given by this generating function so maybe the first question we would like to ask is what is maybe we'll call it a sub even of X which we could define as the sum N equals 0 to infinity of a to n X to the N in other words what if we want the generating function for only the even terms from this sequence or maybe only the odd terms from the sequence or maybe only the multiple of three terms or so on and so forth so now here's what I'll notice along this path is that if we take a of negative x we're going to get the sum N equals 0 to infinity of a n minus X to the N which is going to be the sum N equals 0 to infinity of minus 1 to the N a sub n X to the N great and notice that in in this sum the even terms have positive coefficients in front of the sequence terms and the odd terms have negative coefficients in in front of the sequence terms so what that allows us to do is the following so if we take a of X plus a of negative x we can put these together so this is going to be the sum N equals 0 to infinity of a sub n X to the n plus the sum N equals 0 to infinity minus 1 to the N X sub n X to the N now mashing those sums together we get the sum N equals 0 to infinity of 1 plus minus 1 to the N a sub n X to the N but now it's easy to see that this is 0 if n is odd and it's 2 if n is even so let's see what that gives us that means a of X plus a of minus X is going to be equal to twice the sum of just the even terms so a sub 2 and X to the 2n good so now we're almost to the formula that we want and that is we don't want a 2n up here we just want an end up here and we also don't want this coefficient to out front so what we can do is divide this 2 over and then compose these generating functions with the square root of X instead of just X and that's going to give us our final answer for this I even so what I'll do is I'll clean up the board and then we'll present that final answer ok so we did some calculations on the last board and those calculations quickly follow us to be able to write that the sum N equals 0 to infinity of a sub to n X to the N which we called a sub even X is actually just 1/2 times the quantity a evaluated the square root of x plus a evaluated at negative square root of x which may not seem super helpful but often we have a closed form for these generating functions and so we can simplify that closed form and we'll see that in an example later now you might also ask well what about the odd terms and so we could have the sum N equals 0 to infinity of a sub 2 n plus 1 X to the n so we could maybe call that a odd of X and that's very very similar so that's going to give us 1 over two times the square root of x a root X minus a negative root X so notice we need this extra square root of x in here so let's go ahead and check that that makes sense so this is going to be 1 over 2 root X and now we have the sum N equals 0 to infinity of a and X to the N over 2 so that's the first part and then minus the sum N equals 0 to infinity of minus 1 to the N a sub n X to the N over 2 great so that's what we get by combo composing negative the square root of x in there good so now what we'll notice is that we can put these two together so we have 1 over 2 root X and in the sum N equals 0 to infinity of a sub 1 minus negative 1 to the N a sub n X to the N over 2 but now notice this term right here is 0 if n is even and 2 if n is odd so that means all we get is the odd terms and if you stick an odd term in this n notice that you'll get an extra square root of x which will cancel this thing in the bottom so let's do all the details here so this is 1 over 2 root X and then the sum N equals 0 to infinity of a sub 2 n plus 1 because only we have the odd terms left and then X to the 2n plus 1 over 2 so that's going to be the same thing as X to the n plus 1/2 so let's reiterate 2n plus 1 over 2 will be n plus 1/2 great but now this half will cancel the square root over here and I should say we had a 2 out here so that 2 cancels that 2 good and then the square root of x cancels this half and we're left with exactly what we want okay so I'm going to clean up the board and then we're gonna look at well what if we want a three here instead of a two okay so now we want to look at well what if we want a generating function for the multiples of three and we need a little bit of the theory of the roots of unity in order to do that so let's let ADA equal e to the 2 pi over 3 so notice this is a root of Z cubed minus 1 which can be written as Z minus 1 times Z squared plus Z plus 1 great and in fact we know that this is not equal to 1 which means it's not a root of this part so that means it has to be a root of this portion of that factoring so in other words we have this formula a 2 squared plus a 2 plus 1 equals 0 great so now that now we're going to use that same theory that we used before to construct a generating function with only the multiple of three terms so let's look at the following calculation which will do that we'll take a of X actually let's do maybe a of X to the third plus a of a 2 X to the third plus a of a 2 squared X to the third now notice that's going to be the sum N equals 0 to infinity of a sub n X to the N over 3 so that's this first term plus the sum N equals 0 to infinity of a de to the N a sub n X to the N over 3 and then finally the sum N equals 0 to infinity of ADA to the 2n a sub n X to the N over 3 ok good so now we can put all of these together so that's going to be the sum N equals 0 to infinity of 1 plus a 2 to the n plus a 2 to the 2n times a sub n times X to the N over 3 now the next thing that we want to notice is if 3 divides n then 1 plus a 2 to the n plus a 2 to the 2 N equals 3 ok so let's look at the details of this so if 3 divides n that means N equals 3 times K and now notice that ADA to the N in that case it's really equal to a 2 cubed all to the K power using exponent rules but the fact that ADA is a root of that polynomial we know that a 2 cubed is actually equal to 1 so that makes this equal to 1 and likewise ADA to the 2n is really just ADA cubed to the 2k which is also going to be equal to 1 so that means we get a 3 right here okay so I'm going to erase this part and then we'll look at well what if 3 does not divide n ok so now look we'll look at the case when 3 does not divide in there are actually two cases here will only do one what if N equals 3 k plus 1 and the other case would be N equals 3 k plus 2 so let's see what we've got here so that means ADA to the end is equal to a that to the 3k times eight it to the first power but eighty to the 3k is equal to just a de great but now that means a de to the 2n is equal to a de to the 6k times a2 squared but now that's going to be just a two squared good but what that's going to tell us is that one plus a two to the n plus a to the 2n is the same thing as 1 plus a 2 plus a 2 squared which is equal to 0 given that it's our root of that orange boxed polynomial ok good and then similarly if n is equal to 3 K plus 2 we get the same kind of setup so what we end up with is a 2 here a 2 here and a 1 here and a 1 here and I think we have this is like plus 3 or something ok good so I'm gonna clean up the board and then we'll take it home for a formula for every third term in a sequence ok so on the last board we came up with the following equation so we have a of X to the third plus a of a 2 X to the third plus a of a 2 squared X to the third is equal to this sum 1 plus a to the n plus a 2 to the 2n times a of n equal sorry X to the N over 3 and then also we saw that this was equal to 3 if n was equal to 3 K and it was equal to 0 if n was equal to 3 k plus 1 or 3 k plus 2 good so what that allows us to do is simplify this down to the sum N equals 0 to infinity and only keep the multiples of 3 so in other words we can have this as a 3 that comes out front a sub 3 n X to the N now notice that allows us to solve for a sub 3 which maybe we can define as the sum N equals 0 to infinity of a sub n X sorry a sub 3 n X to the N so this is going to be one third times a X to the third plus a a to X to the third plus a a two squared X to the third like that okay good so now that we've got a feel for how to do these things I'm gonna clean up the board and then we're gonna look at an example okay so I want to do an example involving the Fibonacci numbers because I think they're nice so let's recall that we have F sub 0 is 0 F sub 1 is 1 and then F sub n is defined by this standard two-step recursion so it's n minus 1 plus F sub n minus 2 and that's for n bigger than or equal to 2 and in a previous video we calculated the generating function for the Fibonacci numbers and we found that that was x over 1 minus X minus x squared so I won't read arrived that here so now you want to look at F sub 3 of X so in other words that's going to be the generating function for every third Fibonacci number so we have F sub 3 and X to the N and then by our calculation that we did in general on the last board so that should be 1/3 F X to the third plus F 8 X to the third plus F a dot squared X to the third okay good so now composing that into the generating function which is known we get that this is 1/3 times the quantity X to the third over 1 minus X to the third minus X to the 2/3 plus a de X to the 3rd over 1 minus a 2 X to the 3rd minus a 2 squared X to the 2/3 plus a 2 squared X to the 3rd over 1 minus a 2 squared X to the 3rd minus a 2 to the 4th power but notice a 2 to the 4th power is a 2 cubed times a 2 we know a 2 cubed is 1 so that's just going to be a 2 X to the 2/3 great so now the next thing that we need to do is find a common denominator and the common denominator will be just the product of all of these denominators so let's calculate that real quick so calculating a common denominator we're just going to take the product of all of these so 1 minus X to the 3rd minus X to the 2/3 1 minus a 2 X to the 3rd minus a 2 squared X to the 2/3 1 minus a 2 squared X to the 3rd minus a 2 X to the 2/3 good ok so let's see what we get when we multiply that out so let's first of all look at the constant term so the constant term is just going to be 1 times 1 times 1 so we get 1 for the constant term now the next thing I want to look at is what do we get for the X to the 1/3 term so if we look at the X to the one-third term we're going to get a negative one from this so that'll be negative one there we'll get a negative ADA from that - ADA and then we're going to get a minus a 2 squared from that guy over there so we get a minus a 2 squared for that so but we know that this adds up to 0 by the fact that it's a root of that polynomial that we had on the board before so this is going to become zero great so the next thing we want to do is look at the X to the 2/3 coefficient great and we're going to get that from two different places we're going to get it from just these X to the 2/3 which are part of all of these and then multiplying X to the third with X to the third so let's be careful about that so notice we'll get them from this like I said good so that's again going to be negative 1 minus a 2 minus a 2 squared great and then we also get them from multiplying these guys out from taking two of these things that are yellow circled and then the 1 as the next great so let's see what we get from that so from this and this we get a minus ADA good from taking this one and this one we get a minus a 2 squared okay and then finally from taking this one and this one we get a minus a 2 cubed which is a minus 1 good but now notice that both of these terms are 0 just as before okay fantastic now let's look at the X term so the X to the first power term so great now that's going to come a couple of different ways as well we can get it from multiplying an X to the 3rd to an X to the 2/3 or we can get it by multiplying all of the X to the 3rd so let's first get it by multiplying all of the X to the 3rd x' but notice if we do that we have X to the 3rd negative negative a 2 X to the 3rd negative a 2 squared X to the 3rd so that's going to be an overall a 2 cubed x to the 3 over 3 in other words X so that's going to give us a minus 1 okay so we'll also get it from multiplying the X to the 3rd with X to the 2/3 so we've got several ways that going to happen we could take this X to the third and those two X to the two thirds so let's do that first so taking this X to the third we'll get this a two squared so it's plus a 2 squared plus 8 and those are pluses because everything has a minus sign good now the next way we can do it is taking this X to the third and then the two flanking X to the minus sorry X to the 2/3 so again that's going to give us plus ADA and then plus a 2 squared great so another plus a 2 plus a 2 squared ok fantastic and now one more we could take this X to the third and then these two X to the 2/3 and we're also going to get a plus a 2 plus a 2 squared great but now what we can use here is the fact that all of these add up to negative 1 by the fact that if we recall a 2 squared plus a 2 plus 1 was equal to 0 which means a 2 squared plus a 2 equals negative 1 so we have negative 1 minus 1 minus 1 minus 1 so all of this right here is minus 4 ok good so I'm not going to do the rest of the calculation but it really just involves foiling everything out super carefully and noticing these kind of things with these roots I'll just skip to the end ok so skipping to the end we have the product of all of these denominators is 1 minus 4x minus x squared so we noticed this one and this minus 4 and I'll leave it to you to fill in all of the rest of the details ok good so now once we have this common denominator it's fairly simple although a little bit tedious to simplify out this big term but it's really not that bad so let's just skip to this thing being calculated out so I want to reiterate what you would need to do is put this common denominator and of those rational functions so multiply this whole term by those two denominators multiplied over themselves and so on and so forth so skipping to the generating function for this up here we have the following okay good so skipping to that generating function we have 2x over 1 minus 4x minus x squared so again it's just fairly elementary but tedious okay good so now we have this is equal to this which allows us to come up with some nice combinatorial identities pretty easily for instance let's do the sum N equals 0 to infinity of f sub 3 n over 10 to the N and I will say one thing you have to be careful about the radius of convergence of this I'll let you guys think about how to calculate the radius of convergence for this kind of thing it's not too bad in the end but you do have to worry about that so notice that this is this generating function evaluated at 1 over 10 so that is within the radius of convergence so notice that's going to give us 2 over 10 which is 1 over 5 over 1 minus 4 over 10 which is 2 over 5 minus 1 over 10 squared so that's going to be minus 1 over a hundred so you get something like that but then doing the elementary arithmetic this ends up being 20 over 59 so we've got this nice combinatorial identity involving Fibonacci numbers that we got through this nice new strategy ok this is a nice place to end the video

Channel: Michael Penn

Views: 6,528

Keywords: math, mathematics, number theory, abstract algebra, calculus, differential equations, Randolph College, randolph, Michael Penn, combinatorics, fibonacci, generating functions

Id: BCVPXxNQVIM

Length: 23min 35sec (1415 seconds)

Published: Wed Jan 08 2020