Catalan Numbers | Generating function and closed form. Collaboration with @ProfOmarMath!

okay this is the second of a two-part video where we look at the Catalan numbers so part one is on the YouTube channel Professor Omar math so I urge you guys to check out part 1 of this video a link is in the description in his video he gave a Commodore a combinatorial description of these numbers as well as a recursion which these numbers satisfy so part two of this video is obviously here we're going to construct a generating function and describe a closed form of these numbers so just to pick up where he left off the Catalan numbers can be defined in the following way so C 0 is equal to 1 and then C n plus 1 can be defined in terms of C 0 through C in in the following sum so we have the sum as I goes from 0 to n of C I times CN minus I so notice that's going to be the sum where the first term is raising in its index and the second term is lowering in its index so here we have C 0 CN c 1 c n minus 1 the next one would obviously be C 2 C and minus 2 all the way up to C and C 0 ok so since our goal is to find a generating function in a closed form we're going to need a couple of tools which I will sketch the proof to why these things exist so the first one will be this following sum which is called the Koshi product of two series so we have this infinite power series a I X to the I and then one which is BJ X to the J and if we take their product we get this infinite sum K equals 0 to infinity of this finite sum l equals 0 to K of a sub L times B sub K minus L and then times X to the K ok so we'll go over that first and then the next one that we will need is this binomial coefficient identity so if we look at one half choose n we have that is equal to minus 1 to the n plus 1 divided by 4 to the N times 2 to the n mine one times this thing which is known as a central binomial coefficient which is two in choose n okay and then next we will need another binomial coefficient identity which is one over two times two to the n plus one times two and plus 2 choose n plus 1 is the same thing as 1 over n plus 1 to n choose n ok so now that I've laid out what the Catalan numbers are let's get to proving these identities but first we need to clean up this board ok so I've laid out an array for explaining why this Koshi product is true so notice along the top row I have my first power series so I have a 0 plus a 1 X plus a 2 x squared plus a 3 X cubed and then on my leftmost column I have the power series with a B sub J coefficient so Ivy's 0 plus B 1 X plus B 2 x squared B 3 X cubed and so on and so forth and so if I can if I want to multiply these it will be just like multiplying all the rows and columns if you will so notice in this spot I'm going to get a 0 B 0 and then in this spot I'll get a 1 B 0 times X here we have a 2 B 0 times x squared here we have a 3 times B 0 X cubed ok and now we can fill in the rest of this array in a similar way and here notice I'm going to put plus dot dot dot because that's an infinite sum and now down here I will get plus a 0 B 1 X plus a 0 B 2 x squared plus a 0 B 3 X cubed and then all the way down and now I just need to fill in the middle ok so now in this next row I have a 1 B 1 x squared because I have x times X is x squared and then plus a 2 B 1 x cubed plus a 3 B 1 X to the fourth God dot dot I mean I have pluses going this way as well and now I can continue on so I've got two more rows to do in order to get like a nice picture here so here I'll have a 1 B 2 X cubed a 2 B 2 X to the fourth a 3 B 2 X to the fifth and so on and so forth and then finally down here I'm going to have a 1 B 3 X to the fourth plus a 2 B 3 X to the fifth and then finally a 3 B 3 X to the sixth plus dot dot dot okay great so that gives me some sort of idea for how this is going but now if I look at my diagonals going this way I can see common powers of X so notice everything on this diagonal is X to the 0 power everything on this diagonal is X to the first power everything on this diagonal is X to the 2nd power here we have X cubed and then so on and so forth so X to the 4th who's going to extend up here and then extend down here and then we keep going and going and going so notice that tells us that this product will be a 0 B 0 plus now I'm going to factor an X out of this so we have a 0 B 1 plus a 1 B 0 times X and then I can factor an x squared out of this term so I have a 0 B 2 plus a 1 B 1 plus a 2 B 0 x squared and then so on and so forth ok great but notice that these coefficients clearly have this form right here so notice we're summing we're all products here were these two indices add to K notice L times K minus L is K and that's exactly what's happening right here we're summing over all indices that add to 1 that's the coefficient of x to the first power all embassies that add to 2 that's the coefficient of x squared and so on and so forth ok good so I think we've argued this well enough and now we're ready to move on to the next one ok so now we're going to move on to the second bullet point that we need to prove and we're going to do this by starting at the right-hand side using the definition of the binomial coefficient and then simplifying it until we get the left-hand side so let's start with minus 1 to the n plus 1 over 4 to the N times 2 n minus 1 and then we have 2 n choose n ok and so by the definition of the binomial coefficient I can write that as 2 in quantity factorial over n factorial and then 2n minus n factorial but that's just going to give me a another n factorial so that's good and then I'm going to rewrite minus 1 to the n plus 1 as minus 1 to the N minus 1 because those are clearly the same number n plus 1 and n minus 1 have the same parity and then I'm going to write 4 to the N as 2 to the n times 2 to the N and then we had this 2 to the N minus 1 left ok great now I'm going to expand some of these parts out into a product so I'm going to write this thing as minus 1 to the N minus 1 over now we have this 2 to the N times 2 to the N times 2 to the n minus 1 and now let's write this 2 times n factorial as a descending product so we have 2n times 2n minus 1 times 2n minus 2 all the way down to four times three times two times one so there that numerator is 2 in factorial now I'm going to take one of these in factorials and I'm going to write that as a descending product as well so I'll write it in the following way I'll have n times n minus 1 times n minus 2 would be next all the way down to 2 times 1 so I've spread those out for a reason that we'll see in just a second and then I have one thing left over I have 1 over N factorial left because I haven't done anything with that and now we can do some simplification so notice this guy is going to cancel this guy and turn it into a 2 this guy is going to cancel this guy it's going to turn it into a 2 all the way down we get a 2 there and this guy cancels that into a 2 the last one obviously doesn't really cancel and then how many twos do we have on the top will notice we'll have exactly n twos on the top and that's going to cancel this 2 to the N in the denominator so we'll have all of these cancel this guy right here okay good and then also we have this 2 to the N minus 1 which is going to cancel this 2 to the N minus 1 as well ok so now let's see what we have we have minus 1 to the n minus 1 over 2 to the N ok and notice this thing is going to pick up here at this point that I haven't written which is 2 to the N minus 3 and now I'm going to write this as a rising product instead of a falling product so I can start 1 times 3 times 5 all the way up to 2n minus 3 notice all that's left are the odd numbers so I have 1 times I'm actually going to put another one in there which will be clear a little bit later while I'll do that so I have 1 times 1 times 3 times 5 times 7 all the way up to 2n minus 3 and then this is all over in factorial so one important thing to notice here is that now that I've added this one in there are exactly in terms in this product so what I'm going to do is I'm going to take the in terms of them that in that product and I'm going to put them all over to using this two to the end which is in the denominator so that's going to give me one negative one to the n minus one over N factorial and then that will be multiplied by 1/2 times 1/2 times three halves times five halves all the way up to 2n minus 3 over 2 so that will be my last term ok so on the last board we worked our calculation to here so we have minus 1 to the n minus 1 over N factorial and then 1/2 times 1/2 times three-halves times 5 halves all the way down to 2n minus 3 over 2 now what I want to do is notice that I have a product of n terms in the top sorry in this right-hand bit which means there are n minus 1 terms if I leave off the first half and so what I'll do is I'll take this minus 1 and I will include it in those n minus 1 terms so that's going to give me the following so I'll have 1 over N factorial times one half times minus one half times minus three halves all the way down to 3 minus 2 n over 2 okay good but now let's notice that this is the following so this is going to be one half and then one half minus 1 so we can write negative one half obviously as one half minus one times one half minus two so negative three halves is obviously one half minus two all the way down to one half minus n plus one so this three minus two n over two can also be written as one-half minus n plus one so I'll let you guys check that it's fairly easy to see and then I'll put this all over in factorial but let's see what we have here we have a falling product of in terms starting at one-half over N factorial but that's exactly the definition of the binomial coefficient one-half choose n ok good so that finishes the proof of this next bullet point okay so now we're ready to move on to our third bullet point which is the last of our three tools which we will really need to get a closed form of the Catalan numbers via a generating function so I'll also do this just by direct calculation so notice I have 1 over 2 times 2n plus 1 and then we want to multiply that by the binomial coefficient 2 n plus 2 choose n plus 1 so that's one of these central binomial coefficients I may make a video about just the central binomial coefficients later they had some nice properties on their own okay great so from here we can write this as 1 over 2 times 2n plus 1 and now this is going to be 2n plus 2 factorial over n plus 1 factorial times n plus 1 factorial ok so that's just using the definition of the binomial coefficient and I shouldn't really say the definition but the special case of the binomial coefficient where we have a natural number the definition is actually closer to what we saw with 1/2 choose in on the last board ok so now I'm going to pull some stuff out so in fact what I want to do I'll write this is 1/2 and then 2n plus 1 and now I'll write this as 2 n plus 2 times 2n plus 1 times 2n factorial and then I'll rewrite those two factorials in the denominator as n plus 1 times n factorial and another n plus 1 times n factorial and now let's see what simplification can occur so notice this 2n plus 1 is going to cancel that 2n plus 1 ok and then notice that this two times n plus 1 is going to cancel this 2n plus 2 and that's going to give us exactly after we pull this out 1 over n plus 1 times 2n factorial over n factorial n factorial great but that's exactly what we need it to be ie that is 1 over n plus 1 to n choose n which finishes the proof of this third part ok so now I'm ready to go on to something that's more of my main goal which is to build a generating function for the Catalan numbers and use that to find their closed form and so let's go ahead and set C of X equal to the generating function of the Catalan numbers in other words the sum N equals 0 to infinity of CN times X to the N so our goal will be to find a closed form for this generating function and then re expand it as a power series where we can see a closed form for the Catalan numbers so let's see how we can do that so what I will start with is by pulling they the first term out so notice the first term will be N equals 0 so we have C sub 0 X to the 0 so that's obviously just the number 1 and now I have this is going to be plus the sum N equals 1 to infinity of CN X to the N but now to make this look exactly like our recursion I want to re-index so that I have an n plus 1 there instead of an N so in other words I'm gonna send in 2n plus 1 and that's going to change my start from N equals 0 to n sorry from N equals 1 in equals zero so that's gonna give me one plus the sum N equals zero to infinity of CN plus one times X to the n plus one so the next thing that I want to do is take an X here from this n plus 1 and factor it out to notice that's exactly the same thing if I distribute this X through I'll get X to the n plus 1 now I want to use my recursion so this is going to be 1 plus X times the sum N equals 0 to infinity of the sum I equals 0 to n here I'm using my recursion for the n plus first Catalan number which was derived in the previous video and then we have CI times CN minus I times X to the N but now what we want to do is notice that this looks really really similar to something that's happening in our first bullet point which means that we can write this as 1 plus x times the sum maybe M equals 0 the sum maybe L equals 0 to infinity of CL X to the L times the sum M equals 0 to infinity of CM X to the M ok good so notice this product is going to be the same thing as this infinite sum by this first bullet point but notice each of the terms of this product are just the generating function of the Catalan numbers with the indices renamed so this is exactly equal to 1 plus X times C of x squared okay so now that we have this nice fact we are close to getting a closed form for the Catalan numbers I'll clean up the board and then we'll move on ok so let's see so far we see that C of x equals 1 plus x times of x squared where C of X is the generating function for the Catalan numbers as we described on the last board so notice that's going to give us the following functional equation so we have C of x times x squared minus C of X plus 1 equals 0 ok great now we can go ahead and just use the quadratic formula to solve for C of X and let's see what we get so notice we'll get C of x equals so it'll be negative B so that's going to be 1 because notice B is minus 1 and then we have plus or minus the square root of b squared so that's going to be 1 minus 4 times a times C so notice that's going to be 4 times 1 times X so that'll be minus 4x all over 2a so notice a in this case is X so we get C of x equals this ok great now we want to really figure out well what do I take here as the sine do I need to take the plus or the minus which one is going to make sense so let's notice that we have 1 is equal to C of 0 so that's given in the definition of the Catalan numbers but that should be equal to the limit as X approaches 0 of C of X so I wrote infinity am it X approaches 0 of C of X so what we want to do is calculate that limit in each case to the side if we keep the plus or the minus so let's do that so let's do the limit as X approaches 0 of so let's do the plus first so we have 1 plus the square root of 1 minus 4x over 2 X ok so notice at the moment if we plug X equal 0 into this we will get one plus one on the top so we will get 2 in the numerator and we get zero in the denominator so this is in fact a limit that does not exist I think from the right this is gonna obviously go to positive infinity and from the left this is going to go to negative infinity so either way you do it it just does not exist so that gives us a lot of motivation that this should not be the plus sign we should have the minus sign here but let's go ahead and check that via the limit carefully so let's go ahead and do the limit as X goes to 0 of 1 minus the square root of 1 minus 4x over QX but now notice we have an indeterminate form so if we plug X equal 0 into this we'll get 1 minus 1 over 0 but that's an indeterminate form we could use l'hopital's rule but let's do it a different way let's maybe multiply by the radical conjugates so we have 1 plus the square root of 1 minus 4x 1 plus the square root of 1 minus 4x so we've got something like that going on but notice that's going to give us the limit as X goes to 0 so we've got something like a difference of squares in the numerator so that will give us 1 minus 1 minus 4x over 2x times 1 plus the square root of 1 minus 4x ok great but now notice we have that 1 minus 1 will cancel to 0 and then this minus sign is going to distribute through to make this a plus sign and then this 4x and this 2 X will cancel to give us a 2 in the numerator ok great but now as we send X to 0 here we have 2 in the numerator and we have 2 in the denominator and so that'll be 2 over 2 which is 1 which is exactly what we need it to be so we can go ahead and erase this question mark here of plus or minus and put the minus in because that's what we have okay so I'll clean up the board and then we'll pick up at this point and expand this as a power series using the binomial theorem so in the last board we argued that the generating function for the Catalan numbers are given by one minus the square root of 1 minus 4x over 2 X so I've rewritten it slightly I factored this 1 over 2 X out front and then I have 1 minus the square root of 1 minus 4x and now I just want to point out that here I'm going to use the following well I will use that 1 plus u to the alpha where alpha is really any complex number can be expanded as a infinite series as the sum N equals 0 to infinity of alpha choose in times u to the n ok great so that's the binomial theorem so I know like I proved some things that are maybe like a little simpler than that I could have proven that but we'll just take that as a fact ok so let's see how we can use this so now I'm going to go ahead and rewrite this as 1 over 2x and then 1 minus 1 minus 4 X to the 1/2 power okay which means I can use this binomial theorem with u equal to minus 4x and then alpha equal to 1/2 so let's see what that gives me so that's going to give me 1 over 2x times 1 minus now we have the sum N equals 0 to infinity of 1/2 choose n so that's like my alpha choose n and now u to the n so that will be minus 4x to the nth power so now I want to simplify this a bit ok so now I'm going to use this thing that we proved earlier to rewrite our 1/2 choose in and let's see what we get we get 1 over 2x 1 minus this sum N equals 0 to infinity and then we'll have minus 1 to the n plus 1 over 4 to the N times 2 to the n minus 1 and then we have the central binomial coefficient to n choose in and now we'll have minus 1 to the N times 4 to the n times X to the N so that's from breaking up this minus 4 times X all to the nth power now I'm going to do one more thing I'm going to take this minus 1 to the n plus 1 I'll take one of the minus ones and use that to turn this minus sign out front to a plus and now let's see all of the stuff that can cancel so notice that this minus 1 to the N and this minus 1 to the N are going to cancel with each other this 4 to the N in the denominator and this 4 to the N and the numerator are going to cancel which allows us to rewrite this thing as 1 over 2 X and now we have 1 plus the infinite sum N equals zero to infinity of let's see we have 1 over 2 to the N minus 1 and then 2 n choose in X to the N so I'm gonna go ahead and bring this to the top of the board so we can finish it off so let's see see where we are we have C of X equals 1 over 2 x times the quantity 1 plus this infinite sum so we have N equals 0 to infinity 1 over 2 to the N minus 1 to n choose in X to the N so now what I want to do real quick is pull out the N equals 0 term to see what it is so the N equals 0 term notice we'll have 1 over 0 minus 1 so that'll be negative 1 0 to 0 is 1 X to the 0 is 1 and so the N equals 0 term is negative 1 so what that tells is that if we take this in equals zero term out we can change this to starting at one and then this negative one which we have to take out will cancel this positive one out front now we have one over 2x times the sum N equals 1 to infinity of all of that stuff now the next thing that I want to do is re-index so I'll re index so that in goes to n plus 1 and so that will move this index down so that it starts at 0 so let's see what we get for that that's going to give us 1 over 2x and then we have the sum N equals 0 to infinity of 1 over so if I replace n with n plus 1 there I get 2n plus 1 and then I have 2 n plus 2 choose n plus 1 X to the n plus 1 but now some simplification can happen I'm going to take this 1 over 2 X I'll take the 1/2 and I'll bring it inside and just put it in the denominator there the next thing that I want to do is take this X in the denominator and cancel this X to the n plus 1 down to X to the N but now we've got something that looks like our third bullet point that we proved so notice we have 1 over 2 times 2 to the n plus 1/2 to the n plus 2 choose n plus 1 and that's exactly the left-hand side of this which means I can replace it with the right-hand side so in other words I can replace this with N equals 0 to infinity of 1 over n plus 1 to n choose in X to the N and that is my final closed form for the Catalan numbers because let's recall that this is equal to the sum N equals 0 to infinity of C in X to the N ok so I'm gonna erase the board put a summary up and then do a nice little application of a new combinatorial identity so as a summary we calculated the closed form for the generating function for the Catalan numbers was given by one minus the square root of one minus four x over two x then we expanded that using the binomial theorem and that gave us that the closed form for these Catalan numbers are is given by C sub n is equal to one over n plus one times the central binomial coefficient to n choose n so notice here we can see this like nice quick application and let's say we had the goal of finding the sum as n equals 0 to infinity of CN over 4 to the N but notice that that is exactly equal to the sum N equals 0 to infinity of CN X to the N where we set X equal to 1/4 in other words this is C of 1/4 where C of X is given by this thing up here so notice that is going to be equal to the square root sorry that's going to be equal to 1 minus the square root of 1 minus 4 times 1/4 over 2 times 1/4 and I should say that this is dependent on the fact that 1/4 is within interval of convergence of this function but it is you guys can check that if you want to but notice that this all simplifies down to just the number 2 so I think in the future me and the other channel professor Omar math are going to do more of these collaborations so if you want you can stick a comment either on this video or on the part 1 video of something you might like to see the two of us tackle ok this is a good place to end the video

Channel: Michael Penn

Views: 5,100

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

Id: n6uYe_DmYe8

Length: 32min 43sec (1963 seconds)

Published: Sat Mar 21 2020