3 The Generating Function Method You might have studied,or at least heard of,generating functions.They are a valuable tool in combinatorics.In this section,we start from scratch and show you how to solve recurrences using generating functions. Definition 2 For function T(n)defined on natural numbers,its(ordinary)generating function is 00 G()=>T(i)zi. i=0 What is the generating function G(z)?Why do we need it?It is just another way to express the function T(n)-it carries exactly the same information as T(n),although it looks a bit different.We can easily convert T(n)to its generating function G(z),and vice versa.The advantage of having another expression of the same mathematical object is that sometimes we can process it more easily.For example,in certain situations (which we shall see shortly),finding the generating function of a solution to a recurrence is easier than finding the solution itself.In that case,our strategy is to figure out the generating function first,and then convert it to the actual solution. Bear in mind that,in most cases,we do not worry about whether this sum of infinitely many terms converges, or for what values of z it converges.We are much more interested in the fact that it can be manipulated as a single mathematical object.Hence,a generating function is also called a"formal power series,"which means our main interests are mostly in its form of power series. But why can we find the generating function of a solution?We can attempt to find the solution itself only because it satisfies the original recurrence.What do we know about its generating function,so that we can change our target to the generating function?The answer is,sometimes we can derive an equation for the generating function,from the original recurrence,based on the theorem below. Theorem 4 If G(z)is the generating function of T(n),and c is a constant,then cG(z)is the generating function of T(n).2G()is the generating function ofT(n-1).and is the generating function of S(n)T(i). If Gi(z),G2(z)are the generating functions of T(n),T2(n),respectively,then Gi(z)+G2(z)is the generating function of Ti(n)+T2(n):G(z)G2(z)is the generating function ofT(i)T2(n-i). The proof is trivial and thus skipped.(But please think of why the theorem holds.) Example 5 Solve the recurrence T(m)=3T(n-1)-9T(n-2)+27T(n-3)+(-3)” 3For convenience,we allow n to be equal to 0 here,because otherwise the generating function would not have a constant term.3 The Generating Function Method You might have studied, or at least heard of, generating functions. They are a valuable tool in combinatorics. In this section, we start from scratch and show you how to solve recurrences using generating functions. Definition 2 For function T(n) defined on natural numbers3 , its (ordinary) generating function is G(z) = X∞ i=0 T(i)z i . What is the generating function G(z)? Why do we need it? It is just another way to express the function T(n)—it carries exactly the same information as T(n), although it looks a bit different. We can easily convert T(n) to its generating function G(z), and vice versa. The advantage of having another expression of the same mathematical object is that sometimes we can process it more easily. For example, in certain situations (which we shall see shortly), finding the generating function of a solution to a recurrence is easier than finding the solution itself. In that case, our strategy is to figure out the generating function first, and then convert it to the actual solution. Bear in mind that, in most cases, we do not worry about whether this sum of infinitely many terms converges, or for what values of z it converges. We are much more interested in the fact that it can be manipulated as a single mathematical object. Hence, a generating function is also called a “formal power series,” which means our main interests are mostly in its form of power series. But why can we find the generating function of a solution? We can attempt to find the solution itself only because it satisfies the original recurrence. What do we know about its generating function, so that we can change our target to the generating function? The answer is, sometimes we can derive an equation for the generating function, from the original recurrence, based on the theorem below. Theorem 4 If G(z) is the generating function of T(n), and c is a constant, then cG(z) is the generating function of cT(n), zG(z) is the generating function of T(n−1), and G(z) 1−z is the generating function of S(n) = Pn i=0 T(i). If G1(z), G2(z) are the generating functions of T1(n), T2(n), respectively, then G1(z) + G2(z) is the generating function of T1(n) + T2(n); G1(z)G2(z) is the generating function of Pn i=0 T1(i)T2(n − i). The proof is trivial and thus skipped. (But please think of why the theorem holds.) Example 5 Solve the recurrence T(n) = 3T(n − 1) − 9T(n − 2) + 27T(n − 3) + (−3)n . 3 For convenience, we allow n to be equal to 0 here, because otherwise the generating function would not have a constant term. 7