found by our method of generating function.This is why we had to use the characteristic equation method on top of the generating function method. Sometimes,the generating function method is so powerful that it enables us to solve a seemingly too compli- cated recurrence. Example 6 Solve the recurrence n-2 T(n)= ∑TTm-)-∑TT-i-2), = =0 Solution:The recurrence looks daunting,because the right hand side includes two big sums.But when we examine the sums carefully,we find they are closely related to the generating functions-in fact,they correspond to the generating functions G(z)2 and 22G(2)2,respectively,where G(z)is the generating function of T(n). Therefore,we convert the original recurrence into an equation of the generating functions: G(z)=G（z)2(1-z2), which implies that G(z)=0or G(z)=.So,either T(n)=0,or T(n)= 「1 ifn≡0(mod2) 0 if n=1 (mod 2). 口 Homework Assignment 4 Problem 1 To calculate the product of two polynomials f(x)=ax +b and g(x)=ux2+vx +w,a naive algorithm needs 6 multiplications of coefficients.How can you do better? Problem 2 Prove the number of linearly independent solutions to Equation(4)is equal to the number of distinct roots of its characteristic equation. Problem 3 Solve the following recurrences. (1)T(n)=3T(n-1)+(-3)n. (2)(Chapter 1 Exercise 20 of [8])T(2n)=4T(n)+an+6,T(2n+1)=4T(n)+cn+d,where T(1)=u is given. (3) 3T(n-1)-5T(n-2)ifn=0 (mod 4) T(n)= 6T(m-1)-5T(n-4)fn≡1(mod4) T(n-2) fn≡2(mod4) 2T(n-2) fn≡3(mod4). VT(n+1T(m)where T(1)=1,T(2)=5. (4)(From the Internet,Original Source Unknown)T(n+2)=-T(nyT(n) 9found by our method of generating function. This is why we had to use the characteristic equation method on top of the generating function method. Sometimes, the generating function method is so powerful that it enables us to solve a seemingly too compli￾cated recurrence. Example 6 Solve the recurrence T(n) = Xn i=0 T(i)T(n − i) − nX−2 i=0 T(i)T(n − i − 2). Solution: The recurrence looks daunting, because the right hand side includes two big sums. But when we examine the sums carefully, we find they are closely related to the generating functions–in fact, they correspond to the generating functions G(z) 2 and z 2G(z) 2 , respectively, where G(z) is the generating function of T(n). Therefore, we convert the original recurrence into an equation of the generating functions: G(z) = G(z) 2 (1 − z 2 ), which implies that G(z) = 0 or G(z) = 1 1−z 2 . So, either T(n) = 0, or T(n) =  1 if n ≡ 0 (mod 2) 0 if n ≡ 1 (mod 2). Homework Assignment 4 Problem 1 To calculate the product of two polynomials f(x) = ax + b and g(x) = ux2 + vx + w, a naive algorithm needs 6 multiplications of coefficients. How can you do better? Problem 2 Prove the number of linearly independent solutions to Equation (4) is equal to the number of distinct roots of its characteristic equation. Problem 3 Solve the following recurrences. (1) T(n) = 3T(n − 1) + (−3)n . (2) (Chapter 1 Exercise 20 of [8]) T(2n) = 4T(n) +an+b, T(2n+ 1) = 4T(n) +cn+d, where T(1) = u is given. (3) T(n) =    3T(n − 1) − 5T(n − 2) if n ≡ 0 (mod 4) 6T(n − 1) − 5T(n − 4) if n ≡ 1 (mod 4) T(n − 2) if n ≡ 2 (mod 4) 2T(n − 2) if n ≡ 3 (mod 4). (4)(From the Internet, Original Source Unknown) T(n+2) = √ T(n+1)T(n) T(n+1)2+T(n) 2+1 , where T(1) = 1, T(2) = 5. 9