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