Solution 89: Closed Form of a Generating Function

Share
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.
Any likes, subscriptions, comments, constructive criticisms, etc., are very much appreciated.
For more Weekly Math Challenges:

• *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?

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 Fujiwara Month ago

This is what I tried, and failed.

• Ayushmann _ Month ago

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

Thank you for a nice problem. I hope you can shake off your health problems soon.

• LetsSolveMathProblems  Month 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 Jv Month ago

the 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

• LetsSolveMathProblems  Month 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 Jv Month ago +1

i mean we can have this result only if x

• Hicham Jv Month ago +2

man you re videos are always aweesome thanks for doing this .

• Atharva #breakthrough Month ago +3

Man this Gabriel N guy is amazing?

• reza Month ago +2

Did you catch cold?

• LetsSolveMathProblems  Month ago

I 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 ago

Just 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 Lajunen Month ago +3

Gabriel N. needs harder problems.

• Viola M Month ago +3

What a nice little generating function problem! ðŸ˜Œ I would not have thought to square A!

• Aaron He Month ago +3

9:02 April 1st was 25 days ago

• LetsSolveMathProblems  Month ago +2

I fixed the editing error using the USclip Studio. Thank you for notifying me.

• Mokou Fujiwara Month 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 VincentChui Month ago +1

9:02 how can it go wrong like that?

• LetsSolveMathProblems  Month 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.