Solution:The characteristic equation is 22、 20. Solving this equation,we get two rootseandConsequently,the solution to the homogeneous equation is To(n)=aesn+a2()",where a1,a2 are constants. We guess a particular solution could be linear.2 So we plug T(n)=un +v into the original equation and get that an-)+）+5um-2)+)+a-9)em+号+ed e3 e6 e3+e6 e4 un+v e3+e6 →u= 2·(u-e0+e u=-ue3-2e9e3+e6 e4 2 2v+2+e2 十 Solving the last equation system,we get that u=e,v =0,which means T1(n)=en is a particular solution to the original recurrence.Hence,the total solution is e3 T(m)=To(m+T(m）=a1en+a(-2”+em. 口 Theorems 1,2,and 3,give us a very powerful tool to solve recurrences.Together with methods discussed in future sections,they enable us to solve recurrences in systematics ways.Nevertheless,these theorems and methods are not all we can use when solving recurrences.You will always encounter "strange"recurrences that can never be solved in a systematic way.What can you do in that case?You should bravely guess a solution,just like in the solution of Example 3.Below we do another example that requires you to guess(and prove). Example 4 (USAMO 1990,Day 1.Problem 2)Suppose T(1)=vx2 +48 and T(n+1)=vx2+6T(n)for n 1.Solve the equation T(n)=2x for all positive integer n and all real number x. Solution:Obviously x=+4 satisfies T(1)=2x.Further calculations tell us that for all positive integer n, T(n)=2x in this case. Now we prove there is no other solution.Without loss of generality,we assume z>0. If x 4,then 3x2 48 4x2 2 +48 T(1)<2x.For each positive integer n,we have T(n)<2x→x2+6T(n)<x2+12x<x2+3x2=4z2→T(n+1)<2x. If 4,then 3x2 48 4x2 x2+48 T(1)>2x.For each positive integer n,we have T(n)>2x→x2+6T(n)>x2+12x>x2+3x2=4x2→T(m+1)>2x. Consequently,our initial guess of =4(for all positive integer n)is the only solution. 口 2Don't ask me why.I have no idea about how to make guesses. 6
Solution: The characteristic equation is x 2 − e 3 2 x − e 6 2 = 0. Solving this equation, we get two roots r1 = e 3 and r2 = − e 3 2 . Consequently, the solution to the homogeneous equation is T0(n) = a1e 3n + a2(− e 3 2 ) n , where a1, a2 are constants. We guess a particular solution could be linear.2 So we plug T(n) = un + v into the original equation and get that un + v = e 3 2 (u(n − 1) + v) + e 6 2 (u(n − 2) + v) + (1 − e 3 + e 6 2 )en + e 4 2 + e 7 ⇒ u = e 3 + e 6 2 · (u − e) + e; v = − u(e 3 − 2e 6 ) 2 + e 3 + e 6 2 · v + e 4 2 + e 7 Solving the last equation system, we get that u = e, v = 0, which means T1(n) = en is a particular solution to the original recurrence. Hence, the total solution is T(n) = T0(n) + T1(n) = a1e 3n + a2(− e 3 2 ) n + en. Theorems 1, 2, and 3, give us a very powerful tool to solve recurrences. Together with methods discussed in future sections, they enable us to solve recurrences in systematics ways. Nevertheless, these theorems and methods are not all we can use when solving recurrences. You will always encounter “strange” recurrences that can never be solved in a systematic way. What can you do in that case? You should bravely guess a solution, just like in the solution of Example 3. Below we do another example that requires you to guess (and prove). Example 4 (USAMO 1990, Day 1, Problem 2) Suppose T(1) = √ x 2 + 48 and T(n + 1) = p x 2 + 6T(n) for n ≥ 1. Solve the equation T(n) = 2x for all positive integer n and all real number x. Solution: Obviously x = ±4 satisfies T(1) = 2x. Further calculations tell us that for all positive integer n, T(n) = 2x in this case. Now we prove there is no other solution. Without loss of generality, we assume x ≥ 0. If x > 4, then 3x 2 > 48 ⇒ 4x 2 > x2 + 48 ⇒ T(1) < 2x. For each positive integer n, we have T(n) < 2x ⇒ x 2 + 6T(n) < x2 + 12x < x2 + 3x 2 = 4x 2 ⇒ T(n + 1) < 2x. If x < 4, then 3x 2 < 48 ⇒ 4x 2 < x2 + 48 ⇒ T(1) > 2x. For each positive integer n, we have T(n) > 2x ⇒ x 2 + 6T(n) > x2 + 12x > x2 + 3x 2 = 4x 2 ⇒ T(n + 1) > 2x. Consequently, our initial guess of x = 4 (for all positive integer n) is the only solution. 2Don’t ask me why. I have no idea about how to make guesses. 6
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