Recitation 16 Problem 3. [20 points] A previous problem set introduced us to the Catalan numbers Co, C1, C2,..., where the n-th of them equals the number of balanced strings that can be built with 2n paretheses. Here is a list of the first several of them 42132429143048621679658 Then, in lecture we were all amazed to see that the decimal expansion of the irrational number500000-1000√/24999 1.000001000002000005000014000042000132000429001430004862016796058786208012 encodes"these numbers! Now there are many reasons why one may want to turn to religion, but this revelation is probably not a good one. Let's explain why (a) Let pn be the number of balanced strings containing n('s. Explain why the fol- lowing recurrence hold Po (the empty string for n >1 k=1 Solution. Note that every nonempty balanced string consists of a sequence of one or more balanced strings. The first balanced string in the sequence must begin with a( and end with a"matching"). That is, any balanced string, rn, with n>1('s consists of a balanced string, Sk-1, enclosed in brackets and containing k-1 ('s followed by a balanced string, tn-k, with n-k('s n=(Sk-1)followed by t where 1 <k<n. This observation leads directly to the recurrence (b) Now consider the generating function for the number of balanced strings P(a)=po+plC+p2.c4+P3.'+ Prove that P(ar)=rP(a)+ Solution. We can verify this equation using the recurrence relation (x)2 x(+(Pp1+p1p)x+(p2+p1p1+p2pb)x2+…)+1 1+p2x+(P0p1+p1P0)x2+(P2+pp1+p2p)x23+ t p1C+ p2C-+ p3I� Recitation 16 4 Problem 3. [20 points] A previous problem set introduced us to the Catalan numbers: C0, C1, C2, . . . , where the n­th of them equals the number of balanced strings that can be built with 2n paretheses. Here is a list of the first several of them: n 0 1 2 3 4 5 6 7 8 9 10 11 12 Cn 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 Then, in lecture we were all amazed to see that the decimal expansion of the irrational number 500000 − 1000√249999 1.000001000002000005000014000042000132000429001430004862016796058786208012 . . . “encodes” these numbers! Now, there are many reasons why one may want to turn to religion, but this revelation is probably not a good one. Let’s explain why. (a) Let pn be the number of balanced strings containing n (’s. Explain why the fol￾lowing recurrence holds: p0 = 1, (the empty string) n pn = pk−1 · pn−k, for n ≥ 1. k=1 Solution. Note that every nonempty balanced string consists of a sequence of one or more balanced strings. The first balanced string in the sequence must begin with a ( and end with a “matching” ). That is, any balanced string, rn, with n ≥ 1 (’s consists of a balanced string, sk−1, enclosed in brackets and containing k − 1 (’s, followed by a balanced string, tn−k, with n − k (’s: rn = (sk−1) followed by tn−k where 1 ≤ k ≤ n. This observation leads directly to the recurrence. (b) Now consider the generating function for the number of balanced strings: 3 P(x) = p0 + p1x + p2x 2 + p3x + · · · . Prove that P(x) = xP(x) 2 + 1. Solution. We can verify this equation using the recurrence relation. xP(x) 2 + 1 = x(p0 + p1x + p2x 2 + p3x 3 + · · ·) 2 + 1 = x(p 2 0 + (p0p1 + p1p0)x + (p0p2 + p1p1 + p2p0)x 2 + · · ·) + 1 = 1 + p 2 0x + (p0p1 + p1p0)x 2 + (p0p2 + p1p1 + p2p0)x 3 + · · · = 1 + p1x + p2x 2 + p3x 3 + · · · = P(x)