Problem Set 8 (a) Find a closed-form generating function F(a) for the sequence Solution. From the recurrence equation, this is precisely the sequence (0,1,51-6to,5t2-6t1,5t3-6 We can express this sequence in terms of the generating function F(a) 5t F() 6. -F(a) =(0,5+1,5t1-6to,5t2-6t1,5t3-6t2,)←F(x) The second term is correct; 5to +1=l, since to=0. So we have the equation F(a)=5. F()-6. F(a)+I Solving this equation for F(a) gives: F(a) (b) Rewrite this generating function as a sum of fractions of the form wnere c and r are constant Solution. Factoring the denominator gives 1-5. +6 z2=(1-2x)(1-3c o we can rewrite the fraction in the form 1-5x+6x21-2x1-3 Substituting =0 gives the equation c +d =0. Substituting l gives 1/2 C-d/2 or, equivalently, 2c+d=-1. Solving this system of linear equations gives c=-l and d=1. Therefore, we have 2x1-3 (c) Expand each fraction using the fact 1+rx+r2x2+r3x3+ T Combine these expansions to obtain a closed-form expression for t6 Problem Set 8 (a) Find a closedform generating function F(x) for the sequence (t0, t1, t2, . . .) Solution. From the recurrence equation, this is precisely the sequence: (0, 1, 5t1 − 6t0, 5t2 − 6t1, 5t3 − 6t2, . . .) We can express this sequence in terms of the generating function F(x): ( 0, 5t0, 5t1, 5t2, 5t3, . . . ) ←→ 5xF(x) ( 0, 0, −6t0, −6t1, −6t2, . . . ) −6x2 ←→ F(x) + ( 0, 1, 0, 0, 0, . . . ) ←→ x = ( 0, 5t0 + 1, 5t1 − 6t0, 5t2 − 6t1, 5t3 − 6t2, . . .) ←→ F(x) The second term is correct; 5t0 + 1 = 1, since t0 = 0. So we have the equation: F(x) = 5xF(x) − 6x 2 F(x) + x Solving this equation for F(x) gives: x F(x) = 1 − 5x + 6x2 (b) Rewrite this generating function as a sum of fractions of the form: c 1 − rx where c and r are constants. Solution. Factoring the denominator gives 1 − 5x + 6x2 = (1 − 2x)(1 − 3x). So we can rewrite the fraction in the form: x c d = + 1 − 5x + 6x2 1 − 2x 1 − 3x Substituting x = 0 gives the equation c + d = 0. Substituting x = 1 gives 1/2 = −c − d/2 or, equivalently, 2c + d = −1. Solving this system of linear equations gives c = −1 and d = 1. Therefore, we have: 1 F(x) = −1 + 1 − 2x 1 − 3x (c) Expand each fraction using the fact: 1 = 1 + rx + r 2 x 2 + r 3 x 3 + . . . 1 − rx Combine these expansions to obtain a closedform expression for tn