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

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

LetsSolveMathProblems2 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 BanerjeeMonth agoWhat is your email address

Where we can send you questions ?

Fun With Vaishnavi2 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 H2 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 Ghasa2 months agoIt would be a excellent and welcome step.

With love

Zachary Carson2 months agoJesus Christ is the wmonly way to heaven. Repebt and trust in him

Kai Luigi2 months agodo 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 JosephMonth agoI 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).

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

KarthasisMonth ago@Vampianist3 exactly

Vampianist32 months agoI seems to have re-proven the Cauchy product somewhere along the way ... oh well

Fun With Vaishnavi2 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.

andabata432 months agoSince 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 Gupta2 months agoThe 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 M2 months ago^{+3}1:02 Me: hm, this seems Catalan-y

1:28 Me: oh yeah definitely

LetsSolveMathProblemsMonth ago^{+1}This problem was actually inspired by the generating function of the Catalan numbers. =)

Dave Johnson2 months agoA(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)))

adandap2 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 tapa2 months agorip

JIN ZHI PHOONG2 months agoi.imgur.com/lNXO2Wp.jpg part 1

i.imgur.com/c119Nkc.jpg part 2

Young Sandwich2 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 Sandwich2 months agoFair 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.

LetsSolveMathProblems2 months agoI 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.

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

KarthasisMonth agoMe too

LetsSolveMathProblems2 months ago^{+2}This is precisely my solution, except that I discovered the formula by working backwards. =)