Recitation 16 (c) Find a closed-form expression for the generating function P(a) Solution. Given that P(a)=aP()2+1, the quadratic formula implies that 1土 P(a) If z is small, then P(a) should be about po= 1. Therefore, the correct choice of sign P (d) Show that P(1/100000=5000001000√24999 Solution P(1/100000 1-y1-4/10000 2/1000000 /24999 500000-500000 250000 5000001000√249999 (e) Explain why the digits of this irrational number encode these successive numbers of balanced strings Solution. Suppose that we symbolically carry out the substitution done in the pre- ceding problem part P(x)=p+p1x+p2x2+3x3+ P(10-6)=p+p10-6+m210-12+p310-18+ hus, po appears in the units position, pi appears in the millionths position, p2 ap pears in the trillionths position, and so forthRecitation 16 5 (c) Find a closed­form expression for the generating function P(x). Solution. Given that P(x) = xP (x)2 + 1, the quadratic formula implies that 1 ± √1 − 4x P(x) = . 2x If x is small, then P(x) should be about p0 = 1. Therefore, the correct choice of sign is 1 − √1 − 4x P(x) = . 2x (d) Show that P(1/1000000) = 500000 − 1000√249999. Solution. � P(1/1000000) = 1 − 1 − 4/1000000 2/1000000 �249999 = 500000 − 500000 250000 = 500000 − 1000√ 249999 (e) Explain why the digits of this irrational number encode these successive numbers of balanced strings. Solution. Suppose that we symbolically carry out the substitution done in the pre￾ceding problem part. 3 P(x) = p0 + p1x + p2x 2 + p3x + · · · P(10−6 ) = p0 + p110−6 + p210−12 + p310−18 + · · · Thus, p0 appears in the units position, p1 appears in the millionths position, p2 ap￾pears in the trillionths position, and so forth