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.
    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

Comments • 0

  • LetsSolveMathProblems

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

    • adandap
      adandap Month 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 Fujiwara
      Mokou Fujiwara Month ago

      This is what I tried, and failed.

  • Ayushmann _
    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,.....

  • adandap
    adandap Month ago +1

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

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

      i mean we can have this result only if x

  • Hicham Jv
    Hicham Jv Month ago +2

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

  • Atharva #breakthrough
    Atharva #breakthrough Month ago +3

    Man this Gabriel N guy is amazing?

  • reza
    reza Month ago +2

    Did you catch cold?

    • LetsSolveMathProblems
      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 -
    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
    Topi Lajunen Month ago +3

    Gabriel N. needs harder problems.

  • Viola M
    Viola M Month ago +3

    What a nice little generating function problem! 😌 I would not have thought to square A!

  • Aaron He
    Aaron He Month ago +3

    9:02 April 1st was 25 days ago

    • LetsSolveMathProblems
      LetsSolveMathProblems  Month ago +2

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

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

    9:02 how can it go wrong like that?

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