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. 6Solution: 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