《Mathematics for Computer》Notes for Recitation 16

6.042/18.] Mathematics for Computer Science Apri!8,2005 Srini devadas and Eric Lehman Notes for recitation 16 Problem 1. Find closed-form generating functions for the following sequences. Do not concern yourself with issues of convergence (a)(2,3,5,0,0,0,0.,…) Solution 2+3x+5 (b)(1,1,1,1,1,1,1,) Solution 1+x+x2+x3+...= (c)(1,2,4,8,16,32,64, Solution 1+2x+4x2+8x32+…=(2x)+(2x)2+(2x)2+(2x)3+ (d)(1,0,1,0.,1,0,1,0,…) Solution 1+x2+x4 (e)(0,0,0,1,1,1,1,1, Solution x3(1+x+x2 (f)(1,3,5,7,9.,11

6.042/18.062J Mathematics for Computer Science April 8, 2005 Srini Devadas and Eric Lehman Notes for Recitation 16 Problem 1. Find closed­form generating functions for the following sequences. Do not concern yourself with issues of convergence. (a) �2, 3, 5, 0, 0, 0, 0, . . .� Solution. 2 + 3x + 5x 2 (b) �1, 1, 1, 1, 1, 1, 1, . . .� Solution. 1 3 1 + x + x 2 + x + . . . = 1 − x (c) �1, 2, 4, 8, 16, 32, 64, . . .� Solution. 3 1 3 1 + 2x + 4x 2 + 8x + . . . = (2x) 0 + (2x) + (2x) 2 + (2x) + . . . 1 = 1 − 2x (d) �1, 0, 1, 0, 1, 0, 1, 0, . . .� Solution. 1 4 6 1 + x 2 + x + x + . . . = 1 − x2 (e) �0, 0, 0, 1, 1, 1, 1, 1, . . .� Solution. 3 3 4 5 6 3 3 x x + x + x + x + . . . = x (1 + x + x 2 + x + . . .) = 1 − x (f) �1, 3, 5, 7, 9, 11, . . .�

Recitation 16 Solution d d 1 1+x+x2+x3+ 1+2x+3x2+4xr2+ 2 2+4x+6x2+8x2+ 1+3x+5x2+7x3+ (1-x)

Recitation 16 2 Solution. 1 3 1 + x + x 2 + x + . . . = 1 − x d d 1 1 + x + x 2 + x 3 + . . . = dx dx 1 − x 1 2 1 + 2x + 3x 2 + 4x + . . . = (1 − x ) 2 2 2 2 + 4x + 6x 2 + 8x + . . . = (1 − x ) 2 2 1 3 1 + 3x + 5x 2 + 7x + . . . = (1 − x )2 − 1 − x 1 + x = (1 − x)2

Recitation 16 Problem 2. Find a closed-form generating function for the sequence where tn is the number of different ways to compose a bag of n donuts subject to the following restrictions (a) All the donuts are chocolate and there are at least 3 Solution (b) all the donuts are glazed and there are at most 4 Solution 1 (c) All the donuts are coconut and there are exactly 2 Solution (d) All the donuts are plain and the number is a multiple of 4. Solution (e) The donuts must be chocolate, glazed, coconut, or plan and There must be at least 3 are chocolate donuts There must be at most 4 glazed There must be exactly 2 coconut. There must be a multiple of 4 plain Solution 121-1 x5(1+x2+x3+x4) (1-x)(1-x4)

Recitation 16 3 Problem 2. Find a closed­form generating function for the sequence (t0, t1, t2, . . .) where tn is the number of different ways to compose a bag of n donuts subject to the following restrictions. (a) All the donuts are chocolate and there are at least 3. Solution. 3 x 1 − x (b) All the donuts are glazed and there are at most 4. Solution. 1 − x5 1 − x (c) All the donuts are coconut and there are exactly 2. Solution. 2 x (d) All the donuts are plain and the number is a multiple of 4. Solution. 1 1 − x4 (e) The donuts must be chocolate, glazed, coconut, or plan and: • There must be at least 3 are chocolate donuts. • There must be at most 4 glazed. • There must be exactly 2 coconut. • There must be a multiple of 4 plain. Solution. x3 1 − x5 5 3 1 x (1 + x2 + x + x4) 2 x = 1 − x 1 − x 1 − x4 (1 − x)(1 − x4)

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)

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 forth

Recitation 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

Recitation 16 Problem 4. Consider the following recurrence equation n=0 Tn={2 1 n-1+3Tn-2(n≥ Let f(a) be a generating function for the sequence(T0, T1, T2, T3, (a)Give a generating function in terms of f(a)for the sequence (1,2,2Ti+310,22+3T1,213+312, Solution. We can break this down into a linear combination of three sequences 1,2,0,0,0, 0,T0,T1,T2,T3,…)=xf(x) 0,0,T,T1,T,…)=x2f(x) In particular, the sequence we want is very nearly generated by 1+2 r+ 2 f(ar)+ 3x f(a). However, the second term is not quite correct; were generating 2+2T0=4 instead of the correct value, which is 2. We correct this by subtracting 2.c from the generating function, which leaves 1+2xf(x)+3x2f(x) (b)Form an equation in f(r)and solve to obtain a closed-form generating function Solution. The equation f(x)=1+2rf(x)+3x2f(x) equates the left sides of all the equations defining the sequence To, T1, T2, .with all the right sides. Solving for f(a) gives the closed-form generating function ∫(x) (c) Expand the closed form for f(a)using partial fractions Solution We can write (1+x)(1-3 Thus there exist constants A and B such that: f()

� � � � � Recitation 16 6 Problem 4. Consider the following recurrence equation: ⎧ ⎪⎨ ⎪⎩ 1 n = 0 Tn = 2 n = 1 2Tn−1 + 3Tn−2 (n ≥ 2) Let f(x) be a generating function for the sequence �T0, T1, T2, T3, . . .�. (a) Give a generating function in terms of f(x) for the sequence: �1, 2, 2T1 + 3T0, 2T2 + 3T1, 2T3 + 3T2, . . .� Solution. We can break this down into a linear combination of three sequences: 1, 2, 0, 0, 0, . . . = 1 + 2x 0, T0, T1, T2, T3, . . . = xf(x) 0, 0, T0, T1, T2, . . . � = x2f(x) In particular, the sequence we want is very nearly generated by 1 + 2x + 2xf(x) + 3x2f(x). However, the second term is not quite correct; we’re generating 2 + 2T0 = 4 instead of the correct value, which is 2. We correct this by subtracting 2x from the generating function, which leaves: 1 + 2xf(x) + 3x 2 f(x) (b) Form an equation in f(x) and solve to obtain a closed­form generating function for f(x). Solution. The equation f(x) = 1 + 2xf(x) + 3x 2 f(x) equates the left sides of all the equations defining the sequence T0, T1, T2, . . . with all the right sides. Solving for f(x) gives the closed­form generating function: 1 f(x) = 1 − 2x − 3 2 x (c) Expand the closed form for f(x) using partial fractions. Solution. We can write: 1 − 2x − 3 2 x = (1 + x)(1 − 3x) Thus, there exist constants A and B such that: 1 A B f(x) = = + 1 − 2x − 3x2 1 + x 1 − 3x

Recitation 16 Now substituting a =0 and r=l gives the system of equations 1=A+B 1 A B Solving the system, we find that A=1/4 and B=3/4. Therefore, we have /43/4 1+x (d) Find a closed-form expression for Tn from the partial fractions expansion Solution. Using the formula for the sum of an infinite geometric series gives f(x)=(1-x+x2-x3+x4-…)+(1+3x+32x2+3x32+3x4+…) Thus, the coefficient of xn is: 3 (-1)+x·32

Recitation 16 7 Now substituting x = 0 and x = 1 gives the system of equations: 1 = A + B 1 A B − =4 2 − 2 Solving the system, we find that A = 1/4 and B = 3/4. Therefore, we have: 1/4 3/4 f(x) = + 1 + x 1 − 3x (d) Find a closed­form expression for Tn from the partial fractions expansion. Solution. Using the formula for the sum of an infinite geometric series gives: 1 � � 3 � � 1 − x + x 2 3 4 2 3 4 4 f(x) = 4 − x + x − . . . + 4 1 + 3x + 3 x 2 + 3 x 3 + 3 x + . . . Thus, the coefficient of xn is: 1 3 3n Tn = 4 · (−1)n + 4 ·