Solution:First,the generating function of t(n)=(-3)is g()= Let G(z)be the generating function of T(n).From the recurrence we get that G(z=3zG(z)-9z2G(z)+2723G(z)+9(z) 1 →G(2)= 9() 1-3z+922-272=1-81a=∑3a) i=0 →T(n)= 3n if 4n 0o.w. But we realize this is only a particular solution,not the total solution-we shall get back to this point shortly. In order to find the total solution,we solve the homogeneous equation x3-3x2+9x-27=0÷(x-3)(x2+9)=0, and get one real root 3 and two imaginary roots +3i.4 So the total solution should be T(m)= ∫(a1+1)3mif4n a1·3n 0.w. where al is a constant,if we only care about real numbers.Or we have T(n)= J(a1+1)3n+a2(3i)n+a3(-3i)nif4n a1·3n+a2(3i)n+a3(-3i)n O.W. where a1,a2,a3 are constants,if we consider complex numbers. ◇ We should definitely be happy with the total solution we found above,but are we really happy with the statement that the first part of the solution (i.e.,the part using the generating function)found only a particular solution,not the total solution?In this part of solution,we converted our original recurrence into an equation of generating function,solved the equation to get the generating function,and then converted it back to the solution. It looks like the process should have helped us find all possible solutions of the original recurrence.Why did we find only one particular solution?What did we do wrong? The secret is in the conversion from the original recurrence to the equation of generating function.The original recurrence has an implicit restriction:n 3.In other words,we want the recurrence to hold only when n 3;for the case n 2,there is absolutely nothing we need to worry about.But if you look at the equation of generating function,you immediately see that it has a part concerning the terms of degrees n 2.For example,the constant term of the left hand side must be equal to the sum of the constant terms on the right.This particular part does not belong to the original recurrence;it is what we intentionally added to the original recurrence,in order to use the method of generating function.We paid a cost for adding this part-most solutions to the original recurrence were lost in the conversion;only the solution satisfying the additional part of the equation survived and was finally ADon't confuse the imanginary number i with index i.This symbol is overloaded. PSolution: First, the generating function of t(n) = (−3)n is g(z) = 1 1+3z . Let G(z) be the generating function of T(n). From the recurrence we get that G(z) = 3zG(z) − 9z 2G(z) + 27z 3G(z) + g(z) ⇒ G(z) = g(z) 1 − 3z + 9z 2 − 27z 3 = 1 1 − 81z 4 = X∞ i=0 (3z) 4n ⇒ T(n) =  3 n if 4|n 0 o.w. But we realize this is only a particular solution, not the total solution—we shall get back to this point shortly. In order to find the total solution, we solve the homogeneous equation x 3 − 3x 2 + 9x − 27 = 0 ⇔ (x − 3)(x 2 + 9) = 0, and get one real root 3 and two imaginary roots ±3i. 4 So the total solution should be T(n) =  (a1 + 1)3n if 4|n a1 · 3 n o.w. where a1 is a constant, if we only care about real numbers. Or we have T(n) =  (a1 + 1)3n + a2(3i) n + a3(−3i) n if 4|n a1 · 3 n + a2(3i) n + a3(−3i) n o.w. where a1, a2, a3 are constants, if we consider complex numbers. We should definitely be happy with the total solution we found above, but are we really happy with the statement that the first part of the solution (i.e., the part using the generating function) found only a particular solution, not the total solution? In this part of solution, we converted our original recurrence into an equation of generating function, solved the equation to get the generating function, and then converted it back to the solution. It looks like the process should have helped us find all possible solutions of the original recurrence. Why did we find only one particular solution? What did we do wrong? The secret is in the conversion from the original recurrence to the equation of generating function. The original recurrence has an implicit restriction: n ≥ 3. In other words, we want the recurrence to hold only when n ≥ 3; for the case n ≤ 2, there is absolutely nothing we need to worry about. But if you look at the equation of generating function, you immediately see that it has a part concerning the terms of degrees n ≤ 2. For example, the constant term of the left hand side must be equal to the sum of the constant terms on the right. This particular part does not belong to the original recurrence; it is what we intentionally added to the original recurrence, in order to use the method of generating function. We paid a cost for adding this part—most solutions to the original recurrence were lost in the conversion; only the solution satisfying the additional part of the equation survived and was finally 4Don’t confuse the imanginary number i with index i. This symbol is overloaded. 8