Challenge 89: Can You Find the Generating Function of {a_n}?

Share
Embed
  • Published on Apr 18, 2019
  • Congratulations to Gabriel N., Alon Heller, Minh Cong Nguyen, Rishav Gupta, Kevin Lu, andabata43, fmakofmako, JIN ZHI PHOONG, Florent Bréart, and Fertog for successfully solving the last week's math challenge question! Gabriel N. was the first person to solve the question.
    Welcome, everyone! LetsSolveMathProblems presents one weekly math challenge problem every Wednesday (continental U.S. time). To participate, please comment your proposed answer and explanation below (or discuss potential solutions with other viewers), keeping in mind that your comment should be left unedited to win the recognition prize. Up to the first ten people with correct solutions are recognized in the next challenge video. The solution to a challenge problem is posted as a separate video the following Wednesday.
    For more Weekly Math Challenges:
    usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

Comments • 27

  • LetsSolveMathProblems
    LetsSolveMathProblems  2 months ago +7

    Announcement: Starting with the 101st challenge (or possibly earlier), the Weekly Math Challenge will adopt an email-based problem submission process, featuring problems crafted by any interested viewers. I believe this modification will help diversify not only the contents of the channel (since I can better allocate my time to develop "regular" contents), but also the difficulty and style of Weekly Math Challenges. Further details about the submission process will be announced in the near future. =)

    • Aswini Banerjee
      Aswini Banerjee Month ago

      What is your email address
      Where we can send you questions ?

    • Fun With Vaishnavi
      Fun With Vaishnavi 2 months ago +1

      Yup it's a good step I have been thinking that you should must take this step to increase privacy of solution and also it will help you a lot......!!

    • Johannes H
      Johannes H 2 months ago +1

      I think, there should also be a "secret" way of submitting solutions, so that you don't get spoiled by the correct answers in the comments.
      The solutions may then be made public afterwards. That would be cool.
      In each case, thanks for running this channel!

    • Serengeti Ghasa
      Serengeti Ghasa 2 months ago

      It would be a excellent and welcome step.
      With love

  • Zachary Carson
    Zachary Carson 2 months ago

    Jesus Christ is the wmonly way to heaven. Repebt and trust in him

  • Kai Luigi
    Kai Luigi 2 months ago

    do i need to know about generating functions or just some prior knowledge on taylor polynomials is enough because i haven't the faintest idea on how to solve this ;-;

    • Jody Joseph
      Jody Joseph Month ago

      I brushed up on sequences and infinite series, limits (why only the negative root?) and convergence, series products (Catalan, Cauchy), generating functions (z-transforms), and algebraic manipulation (traversing binomial theorem and combinations, even the figurates). Still didn't quite get it (didn't make it to rigour and proof).

  • Vampianist3
    Vampianist3 2 months ago +1

    Too late to be the first one, so I'll go for an interesting solution that I came up with. If it's actually written somewhere it's completely coincidental ~
    Although the iterative expression works for only n>1, it will be useful to see what RHS evaluates to when n=1, and we see that RHS evaluates to 0. Now, multiplying both sides by x^n and summing both sides from 0 to infinity gives
    sum_{n=0}^{inf} (a_n*x^n)
    =1+x+sum_{n=2}^{inf}(a_n*x^n)
    =1+x+sum_{n=2}^{inf}[sum_{i=n-1}^{inf}(a_i(a_{n-i-1}-1))x^n]
    =1+x+sum_{n=1}^{inf}[sum_{i=n-1}^{inf}(a_i(a_{n-i-1}-1))x^n]
    (changing n from 2 to 1 makes no difference because we are effectively adding a 0) Now, interchange the order of summation (of course change the bounds as well, much like changing the order of integration)
    =1+x+sum_{i=0}^{inf}[sum_{n=i+1}^{inf}(a_i(a_{n-i-1}-1))x^n]
    since a_i is independent of n, we can bring it outside the inner sum. Also, we make the substitution k=n-i-1
    =1+x+sum_{i=0}^{inf}[a_i*sum_{k=0}^{inf}(((a_k)-1)x^(k+1+i))]
    now, bring x^i out of the inner sum as well because it's independent of k, we see that the rest is independent of i, so we effectively have two sums
    =1+x+[sum_{i=0}^{inf}(a_i*x^i)]*[sum_{k=0}^{inf}((a_k)-1)x^(k+1)]
    =1+x+A(x)*[(sum_{k=0}^{inf}(a_k*x^(k+1)))-(sum_{k=0}^{inf}x^(k+1))]
    =1+x+A(x)*[x*A(x)-(sum_{k=0}^{inf}x^(k+1))]
    since this is about generating function, we don't need to worry about convergence issue. So the sum in the last line simply evaluates to (1/(1-x))-1, hence we have
    A=1+x+A*[x*A-(1/(1-x))+1]
    or
    x(1-x)A^2-A+(1-x^2)=0
    using the root formula gives the result. Note that we discard the one with the + sign because when plugging in x=0 (which is within the radius of convergence, so works), the one with the + sign explodes to infinity. The one with the - sign has the limit of 1 as x approaches 0 (using L'Hopital's rule, which is kinda trivial compared with what I wrote above so I'll omit this part...), which is what should happen.
    Phew! That's a lot of sums! Hopefully it is not too messy and makes sense.

    • Karthasis
      Karthasis Month ago

      @Vampianist3 exactly

    • Vampianist3
      Vampianist3 2 months ago

      I seems to have re-proven the Cauchy product somewhere along the way ... oh well

  • Fun With Vaishnavi
    Fun With Vaishnavi 2 months ago +2

    It can simply proved by taking limit x tend to 0 of A(x) .
    Because A(x) can be written as a0.x^0 +a1.x^1+a2.x^2 +a3.x^3 +..........
    And we know that A(0)=a0=1
    So limit tending to 0 A(x) gives one .
    Hence proved.

  • andabata43
    andabata43 2 months ago

    Since the proposed closed form for A(x) is a solution of the quadratic x(x-1)U^2 - U +(1-x^2) = 0 in U, it is sufficient to show the series for A(x) satisfies x(1-x)(A(x))^2-A(x)+(1-x^2) = 0. Rearranging the latter gives A(x)/(1-x) = x(A(x)^2) +(1+x). Rearranging the definition of a_n shows it is equivalent to Sum[a_k, {k,0,n}] = Sum[(a_j)(a_(n-1-j), {j,0,n-1}]. Note for any function f(x) = Sum[ (c_k)(x^k), {k,0,Inf}], we have f(x)/(1-x) = Sum[ (b_k)(x^k), {k,0,Inf}] where b_k = Sum[c_j, {j,0,k}], and (f(x))^2 = Sum[ (d_k)(x^k), {k,0,Inf}] where d_k = Sum[(c_j)(c_(k-j), {j,0,k}]. Applying this to A(x), we have A(x)/(1-x) = Sum[ (B_n)(x^n), {n,0,Inf}] where B_n = Sum[a_j, {j,0,n}], and also x*(A(x))^2 = Sum[ (D_(n-1))(x^n), {n,1,Inf}] , where D_(n-1) = Sum[(a_j)(a_(n-1-j), {j,0,n-1}]. Direct substitution into the rearranged quadratic in A(x), with addition of the term (x+1) to adjust for the initial given values of a_0 and a_1, shows the equivalence of coefficients of x^n, and proves the result.

  • Rishav Gupta
    Rishav Gupta 2 months ago

    The expression of a_n can be written ad
    a_n+1=(a_0a_n+a_1a_(n-1)........a_na_0)-
    (a0+a1+a2.....an)
    BY summing from n=1to infinity and adding and subtracting constant terms
    Coof of x^n in( A-1/x)-1=coof of x^n in(A^2)-coof of x^n in (A/1-x)
    (A-1-x/x)=(A^2(1-x)-A)/1-x
    The following expression of can be simplified to get a quadratic eqn from where one of the root has same expression as suggested in qn and the other has + ve sign before the root but from 2nd root we cant get A(0)=1 Since constant term is 1 we should get A(0)=1 which is satiafied only by -ve one

  • Viola M
    Viola M 2 months ago +3

    1:02 Me: hm, this seems Catalan-y
    1:28 Me: oh yeah definitely

    • LetsSolveMathProblems
      LetsSolveMathProblems  Month ago +1

      This problem was actually inspired by the generating function of the Catalan numbers. =)

  • Dave Johnson
    Dave Johnson 2 months ago

    A(x) and its derivatives are not defined at 0 unless you rearrange to get the radical in the denominator, like so:
    A(x) = (2(1-x^2)) / (1 + √(1 - 4x(1-x)(1-x^2)))

  • adandap
    adandap 2 months ago +1

    Yes! Slogging through all of the examples and problems in Bender and Orszag has paid off! If we multiply the given difference equation by x^n and sum from n=0 to infinity on both sides, we can turn it into an algebraic equation after a little algebra on the RHS. Specifically, the LHS becomes (A-1)/x and the RHS is (1-x) A^2 -x. So the equation is x(1-x) A^2 - A + 1-x^2 =0, which has two solutions of the form of the stated answer with + or - in front of the sqrt. Only the -ve root gives A(0) = 1.

  • el tapa
    el tapa 2 months ago

    rip

  • JIN ZHI PHOONG
    JIN ZHI PHOONG 2 months ago

    i.imgur.com/lNXO2Wp.jpg part 1
    i.imgur.com/c119Nkc.jpg part 2

  • Young Sandwich
    Young Sandwich 2 months ago +1

    I got last week’s right but wasn’t featured in the video, rip. I was 7th to answer it too.

    • Young Sandwich
      Young Sandwich 2 months ago

      Fair enough. I did the whole induction on paper but it was way to long (half a written page). (Having to stagger the base case tripped me up the first run through)
      Also, that is false, but the limit of that left hand side approaches the right hand side, I believe I stated that in my answer, in fewer words (probably should have used arrows instead of equal signs but meh). Doesn’t really matter now though.

    • LetsSolveMathProblems
      LetsSolveMathProblems  2 months ago

      I did review your solution prior to filming this video, but I felt your answer was not comprehensive or clear enough to merit a recognition. For example, you stated that "|sqrt((n+1+x_n)/(n+1))/x_n|=|1/x_n|," which seems evidently false. Even if the limit as n -> inf was implied on both sides of the equation, you still did not prove that the limit of sqrt((n+1+x_n)/(n+1)) is 1, so the argument would not be complete. For this particular challenge, only the solutions that I believed were completely rigorous were recognized (for example, the existence of limit should not be assumed without proof). However, I do admit that I may have made errors in determining the line between informality and formality.

  • LetsSolveMathProblems
    LetsSolveMathProblems  2 months ago +2

    Due to busy schedule, the solution to the last week's problem will be posted tomorrow (Thursday). I sincerely apologize for the delay. The solution to the last week's problem is 1.

  • Gabriel N.
    Gabriel N. 2 months ago +2

    Well, this is equivalent of proving that A obey the quadratic:
    x(1-x)A^2-A+ 1-x^2=0
    Since the other solution does not have the same initial coefficients, that is, it does not converge around 0.
    Furthermore, we write:
    A-x-1=x(A^2-A/{1-x})
    The fact that this is implied by the conditions is merely an application of the Cauchy Product.
    Hence, we have the result.
    QED.

    • Karthasis
      Karthasis Month ago

      Me too

    • LetsSolveMathProblems
      LetsSolveMathProblems  2 months ago +2

      This is precisely my solution, except that I discovered the formula by working backwards. =)