# Solution 89: Closed Form of a Generating Function

Embed

- We algebraically manipulate the generating function of a Catalan-like sequence to find its closed form.

Congratulations to Gabriel N., JIN ZHI PHOONG, adandap, Rishav Gupta, andabata43, and Vampianist3 for successfully solving this math challenge question! Gabriel N. was the first person to solve the question.

Your support is a heartfelt source of encouragement that propels the channel forward.

Please consider taking a second to subscribe in order to express your valuable support and receive notifications for the latest videos!

Any likes, subscriptions, comments, constructive criticisms, etc., are very much appreciated.

For more Weekly Math Challenges:

usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

LetsSolveMathProblemsMonth ago^{+8}*Extra: The famous and ubiquitous Catalan numbers can be defined by recurrence as follows: C_0 = C_1 = 1 and C_n = sum of C_i * C_(n-1-i) as i ranges from 0 to n-1. Can you find the closed form of the generating function of the Catalan numbers?

adandapMonth ago^{+1}Yes, and it's very similar to this problem. Call the generating function C(x). Multiply both sides of the recurrence relation by x^n and sum from 1 to infinity. The LHS is simply C(x) -1 and the RHS is just x [C(x)]^2 using Cauchy's product. So you get x C^2 - C + 1 = 0, which has solution C(x) = (1 - sqrt(1 - 4 x) )/(2 x) when you insist that C(0) =1. (A generalisation of this is example 2.5.1 in Bender and Orszag)

Mokou FujiwaraMonth agoThis is what I tried, and failed.

Ayushmann _Month agoHow to solve questions like find the generating function in closed form for the sequence of real no 0,0,0,1,1,1,1,.....

adandapMonth ago^{+1}Thank you for a nice problem. I hope you can shake off your health problems soon.

LetsSolveMathProblemsMonth ago^{+1}Thank you so much for your kind words! Unfortunately, I am still struggling with sore throat, although it is getting better. I was at Boston over the weekend and made a very wrong choice to bring only a thin jacket, which did not help me recover from cold at all. (The fact that I was walking around at an average of 25,000+ steps for three days did not help.) I do hope to get better soon and make more content once the summer break commences. =)

Hicham JvMonth agothe video was so clear and awesome as usual but at 8:20 we have A(x)+xA(x)+x^2A(x)+.....=A(x)*((1-x^n)/1-x)

so how we get A(x)+xA(x)+x^2A(x)+.....=A(x)/1-x

LetsSolveMathProblemsMonth ago^{+1}When computing a generating function, we often perform what is termed a "formal manipulation," which means that we intuitively manipulate the expression without being too rigorous (e.g., worrying about when the expression converges). To borrow Herbert Wilf's words (he wrote a famous book titled "generatingfunctionology"), a generating function "is a clothesline on which we hang up a sequence

of numbers for display." The main purpose of a generating function is to succinctly summarize the terms of our sequence in a compact, formal manner, and we do not care much about the convergence issues, such as the magnitude of the common ratio being less than 1.

Hicham JvMonth ago^{+1}i mean we can have this result only if x

Hicham JvMonth ago^{+2}man you re videos are always aweesome thanks for doing this .

Atharva #breakthroughMonth ago^{+3}Man this Gabriel N guy is amazing?

rezaMonth ago^{+2}Did you catch cold?

LetsSolveMathProblemsMonth agoI have caught cold and am still recovering from it. Hopefully my sore throat did not detract too much from the explanation. I will try to get better soon. =)

DucassiiiN -Month agoJust for fun I got the simplified expression from the cuadratic formula of A(x), and then substituted the given cuadratic expression of A(x) in it, but that led me to the conclusion that x=0... Does this make any sense?

Topi LajunenMonth ago^{+3}Gabriel N. needs harder problems.

Viola MMonth ago^{+3}What a nice little generating function problem! ðŸ˜Œ I would not have thought to square A!

Aaron HeMonth ago^{+3}9:02 April 1st was 25 days ago

LetsSolveMathProblemsMonth ago^{+2}I fixed the editing error using the USclip Studio. Thank you for notifying me.

Mokou FujiwaraMonth ago^{+4}A really difficult problem that I can't solve before solution is out, even I watched the video I don't even fully understand. I will try to do it again and understand this problem.

2005 VincentChuiMonth ago^{+1}9:02 how can it go wrong like that?

LetsSolveMathProblemsMonth ago^{+4}I fixed the editing error in the USclip Studio. Thank you for notifying me.

*Edit: For the interested viewers, I accidentally put two different video clips on top of each other during the editing process, making them play simultaneously for a few seconds. Fortunately, the problem portion did not contain any important explanation, so I decided to crop it out post-upload via USclip's editing system.