Recursive Algorithm and Recurrence Relations Instructor:Sheng Zhong December 9,2020 1 Karatsuba Algorithm:One Example of Recursive Algorithms We learned multiplication in primary school.When we do 12 x 34,we essentially calculate 1 x 2 x 100+(2 x 3+1×4)×l0+2×4.In general,.we use the formula 2n-2 =01=0 where b=10 for decimal calculations,while b is often equal to some power of 2 in computers.This naive algorithm needs to do(2n-1)(n-1)"basic"multiplications (i.e.,multiplications over [0,b-1])in order to multiply two number from0-1].Naturally,one might suspect this is the best we could do,because there seems no obvious way to do it faster. Surprisingly,Russian mathematician Anatoly Karatsuba proposed a counter-intuitive algorithm that easily beats the naive algorithm for multiplication.The idea is quite simple:when you do 12 x 34,you should not waste your time doing two "basic"multiplications for(2 x 3+1 x 4).In stead,you should just calculate (1+2)×(3+4)-1×4-2×3,which is identical to(2×3+1×4).Noticing that you have to calculate 1 x 4 and 2x 3 for other parts of the expression anyway,for this specific part you just need to do one "basic" multiplication!Therefore,we have reduced the total amount of work. Below we present a straightforward recursive algorithm based on Karatsuba's idea. Algorithm karatsuba(,y) if (x <2)or (y 20) return xy; split in the middle and get (h,l); split y in the middle and get (hy,ly); ro karatsuba(lz,ly); r1=karatsuba((l+hz),(ly +hy)); r2 karatsuba(h,hy); return the number r2·22b+(r1-T2-ro）.2b+ro:
Recursive Algorithm and Recurrence Relations Instructor: Sheng Zhong December 9, 2020 1 Karatsuba Algorithm: One Example of Recursive Algorithms We learned multiplication in primary school. When we do 12 × 34, we essentially calculate 1 × 2 × 100 + (2 × 3 + 1 × 4) × 10 + 2 × 4. In general, we use the formula ( nX−1 i=0 xi · b i ) · ( nX−1 i=0 yi · b i ) = 2 Xn−2 i=0 ( X i j=0 xjyi−j ) · b i , where b = 10 for decimal calculations, while b is often equal to some power of 2 in computers. This naive algorithm needs to do (2n − 1)(n − 1) “basic”multiplications (i.e., multiplications over [0, b − 1]) in order to multiply two number from [0, bn−1 − 1]. Naturally, one might suspect this is the best we could do, because there seems no obvious way to do it faster. Surprisingly, Russian mathematician Anatoly Karatsuba proposed a counter-intuitive algorithm that easily beats the naive algorithm for multiplication. The idea is quite simple: when you do 12 × 34, you should not waste your time doing two “basic” multiplications for (2 × 3 + 1 × 4). In stead, you should just calculate (1 + 2) × (3 + 4) − 1 × 4 − 2 × 3, which is identical to (2 × 3 + 1 × 4). Noticing that you have to calculate 1 × 4 and 2 × 3 for other parts of the expression anyway, for this specific part you just need to do one “basic” multiplication! Therefore, we have reduced the total amount of work. Below we present a straightforward recursive algorithm based on Karatsuba’s idea. Algorithm karatsuba(x, y) if (x < 2 b ) or (y < 2 b ) return xy; split x in the middle and get (hx, lx); split y in the middle and get (hy, ly); r0 = karatsuba(lx, ly); r1 = karatsuba((lx + hx),(ly + hy)); r2 = karatsuba(hx, hy); return the number r2 · 2 2b + (r1 − r2 − r0) · 2 b + r0. 1
Now,assume that each"basic"multiplication is on a couple of b-bit integers,and that the Karatsuba algorithm needs T(n)"basic"multiplications on a couple of n-bit numbers.Assuming the multiplication of le+h and ly+hy requires no more"basic"multiplication than the multiplication ofl and ly(or that of h and hy),we get the following equation: Tm)=37(5, (1) It is trivial to derive from the above equation that T(n)=3og2T(b)=()og23nlog23,assuming b is small and n is big.In contrast,the naive algorithm needs at least n2"basic"multiplications.For large n,the difference can be very significant. The Karatsuba algorithm is the beginning of a search for formulae that helps reduce the computational cost of multiplication.Many more formulae have been found since then.For example,in 2009,Fan and his collaborators developed a number of Karatsuba-like formulae,including some asymmtric ones.Interested readers can refer to[6]. One might find it interesting to solve recurrence relations like Eq.(1).It turns out that there is no universal approach to solve all recurrence equations.Hereafter we examine a few types of recurrences that we know how to solve. 2 Recurrences,Total and Particular Solutions We say a recurrence is linear if T(n)is equal to a linear combination of T(m)s (m n).For a large class of linear recurrences,we happen to know the structure of their solutions,which is quite analogous to that of linear system solutions. Theorem 1 The set of solutions to the linear recurrence T(m)=∑cT(an+b)+d(n,(n≥no) (2) i=1 (where ain +bi n for all i and all n no)is {To(n)+T(n)To(n)=>cTo(ain+bi)}, =1 where T(n)is an arbitrary solution to Equation (2).Since T(n)itself belongs to the set of solutions,we usually call it a particular solution and the set of all solutions the total solution. Hereafter,we are sloppy in writing things like T(because T is defined on positive integers butmay not be an integer.However. all our discussions hold when we replace with and do some minor modifications.Hence,to keep it simple,we use expressions like T()as if they were legal
Now, assume that each “basic” multiplication is on a couple of b-bit integers, and that the Karatsuba algorithm needs T(n) “basic” multiplications on a couple of n-bit numbers.Assuming the multiplication of lx + hx and ly + hy requires no more “basic” multiplication than the multiplication of lx and ly (or that of hx and hy), we get the following equation:1 T(n) = 3T( n 2 ). (1) It is trivial to derive from the above equation that T(n) = 3log2 n b T(b) = (n b ) log2 3 ≈ n log2 3 , assuming b is small and n is big. In contrast, the naive algorithm needs at least n 2 “basic” multiplications. For large n, the difference can be very significant. The Karatsuba algorithm is the beginning of a search for formulae that helps reduce the computational cost of multiplication. Many more formulae have been found since then. For example, in 2009, Fan and his collaborators developed a number of Karatsuba-like formulae, including some asymmtric ones. Interested readers can refer to [6]. One might find it interesting to solve recurrence relations like Eq. (1). It turns out that there is no universal approach to solve all recurrence equations. Hereafter we examine a few types of recurrences that we know how to solve. 2 Recurrences, Total and Particular Solutions We say a recurrence is linear if T(n) is equal to a linear combination of T(m)s (m < n). For a large class of linear recurrences, we happen to know the structure of their solutions, which is quite analogous to that of linear system solutions. Theorem 1 The set of solutions to the linear recurrence T(n) = X k i=1 ciT(ain + bi) + d(n),(n ≥ n0) (2) (where ain + bi < n for all i and all n ≥ n0) is {T0(n) + T1(n)|T0(n) = X k i=1 ciT0(ain + bi)}, where T1(n) is an arbitrary solution to Equation (2). Since T1(n) itself belongs to the set of solutions, we usually call it a particular solution and the set of all solutions the total solution. 1Hereafter, we are sloppy in writing things like T( n 2 ) because T is defined on positive integers but n 2 may not be an integer. However, all our discussions hold when we replace n 2 with b n 2 c and do some minor modifications. Hence, to keep it simple, we use expressions like T( n 2 ) as if they were legal. 2
Proof:Consider T(m)=∑T(a:n+b) (3) i=1 Equation (3)has all terms being of degree 1,and is thus called a homogeneous equation.Suppose To(n)is a solution to Equation(3)and T1(n)a solution to Equation(2).Easy to get that Ti(n)+To(n)= ∑c五(a,n+b)+d(n)+∑aT(ain+b) i=1 =1 k >ci(Ti(ain+bi)+To(ain+bi))+d(n). =1 Hence,Ti(n)+To(n)must also be a solution to Equation (2). Conversely,if T2(n)is a solution to Equation (2),we can easily verify that T2(n)-T1(n)is a solution to Equation(3).Therefore,T2(n)can be written as the sum of T1(n),a particular solution,and a solution to the homogenous equation. 口 Example 1 Solve the recurrence T=2T()-1. Solution:Clearly the corresponding homogeneous equation has solutions To(n)=kn where k is an arbitrary constant.A particular solution is T(n)=1.Hence,the total solution is T(n)=kn +1. ▣ Nevertheless,homogeneous equations are not always so easy to solve.In many cases,we do not know how to solve it and have to rely on the"guess-and-prove"stragtegy.Below we discuss one(unusual)type of homogeneous equations for which we do have a systematic approach. Definition 1 Consider the homogeneous equation T(n)=cT(m-1)+c2T(n-2)+..+ckT(n-k), (4) where k is a constant positive integer,c1,...,ck are all constants,and cick 0.We say Equation (4)is a linear homogeneous recurrence with constant coefficients of order k.Its characteristic equation is kciak-1-c2xk-2...-ck 0. (5) If you have studied linear algebra,please compare the above definition with the characteristic equation of a real symmetric matrix.If you have studied differential equations,please compare the above definition with the characteristic equation of a linear differential equation with constant coefficients of order k.The comparison will help you understand the deep connection between Equations(4)and(5),which is reflected by the theorem below. Theorem 2 If Equations (5)has k distinct roots r1,...,rk.then the solutions to Equation (4)are To(n)=air?a2r2 +...akre, where a1,...,ak are constants.There is no other solution to Equation (4)
Proof: Consider T(n) = X k i=1 ciT(ain + bi). (3) Equation (3) has all terms being of degree 1, and is thus called a homogeneous equation. Suppose T0(n) is a solution to Equation (3) and T1(n) a solution to Equation (2). Easy to get that T1(n) + T0(n) = X k i=1 ciT1(ain + bi) + d(n) +X k i=1 ciT0(ain + bi) = X k i=1 ci(T1(ain + bi) + T0(ain + bi)) + d(n). Hence, T1(n) + T0(n) must also be a solution to Equation (2). Conversely, if T2(n) is a solution to Equation (2), we can easily verify that T2(n) − T1(n) is a solution to Equation (3). Therefore, T2(n) can be written as the sum of T1(n), a particular solution, and a solution to the homogenous equation. Example 1 Solve the recurrence T(n) = 2T( n 2 ) − 1. Solution: Clearly the corresponding homogeneous equation has solutions T0(n) = kn where k is an arbitrary constant. A particular solution is T1(n) = 1. Hence, the total solution is T(n) = kn + 1. Nevertheless, homogeneous equations are not always so easy to solve. In many cases, we do not know how to solve it and have to rely on the “guess-and-prove” stragtegy. Below we discuss one (unusual) type of homogeneous equations for which we do have a systematic approach. Definition 1 Consider the homogeneous equation T(n) = c1T(n − 1) + c2T(n − 2) + . . . + ckT(n − k), (4) where k is a constant positive integer, c1, . . . , ck are all constants, and c1ck 6= 0. We say Equation (4) is a linear homogeneous recurrence with constant coefficients of order k. Its characteristic equation is x k − c1x k−1 − c2x k−2 − . . . − ck = 0. (5) If you have studied linear algebra, please compare the above definition with the characteristic equation of a real symmetric matrix. If you have studied differential equations, please compare the above definition with the characteristic equation of a linear differential equation with constant coefficients of order k. The comparison will help you understand the deep connection between Equations (4) and (5), which is reflected by the theorem below. Theorem 2 If Equations (5) has k distinct roots r1, . . . , rk, then the solutions to Equation (4) are T0(n) = a1r n 1 + a2r n 2 + . . . + akr n k , where a1, . . . , ak are constants. There is no other solution to Equation (4). 3
Proof:First,since r1,...,rk are roots of Equation (5),for i=1,...,k,we have -car-1-c2r-2-.-c以=0→r=r-1+c2r-2+.+ekr-* Hence. To(n)air a2r2+...+akre =a1(Gr1-1+c2r-2+.+cgr-k+.+ak(C1r-1+2r-2+.+cgr-) =G(a1r1-1+a2r2-1+.+ar-1)++c4(a11-k+a2r3-k++ar-k ciTo(n-1)+...+ckTo(n-k), which means To(n)satisfies Equations (4). Next,we show there is no other solution to Equation (4).Suppose S(n)is a solution to Equation(4),i.e., S(n)=cS(m-1)+c2S(n-2)+..+ckS(n-k) Now,consider the linear system (with unknowns a1,...,an) a1r1+a22+..+akTk=S(1) a1r+a2r吃+..+akr2 =S(2) airf +a2r+...+akr S(k). The coefficient matrix of the left hand side can be viewed as the product of a Vandermonde matrix and a diagonal matrix: T2 Tk 0 0 0 0 Tk Consequently,the coefficient matrix must be full-rank,and the linear system must have a(unique)solu- tion.When we use this solution as the constants in To(n),we are guaranteed that To(1)=S(1),To(2)= S(2),...,To(k)=S(k).A simple induction on n allows us to extend this result to To(n)=S(n)for all positive integer n,because both To()and S()satisfy the same recurrence. 口 Example 2 A function T:++satisfies the following conditions: ·For all n1,n2∈Z+such that ged(n1,n2)=1,T(n1n2）=T(m1)T(n2). ·For all m,n∈2+(m≥2，.T(mn)=ma- (T(mn-2庐. Find the function T
Proof: First, since r1, . . . , rk are roots of Equation (5), for i = 1, . . . , k, we have r k i − c1r k−1 i − c2r k−2 i − . . . − ck = 0 ⇒ r n i = c1r n−1 i + c2r n−2 i + . . . + ckr n−k i . Hence, T0(n) = a1r n 1 + a2r n 2 + . . . + akr n k = a1(c1r n−1 1 + c2r n−2 1 + . . . + ckr n−k 1 ) + . . . + ak(c1r n−1 k + c2r n−2 k + . . . + ckr n−k k ) = c1(a1r n−1 1 + a2r n−1 2 + . . . + akr n−1 k ) + . . . + ck(a1r n−k 1 + a2r n−k 2 + . . . + akr n−k k ) = c1T0(n − 1) + . . . + ckT0(n − k), which means T0(n) satisfies Equations (4). Next, we show there is no other solution to Equation (4). Suppose S(n) is a solution to Equation (4), i.e., S(n) = c1S(n − 1) + c2S(n − 2) + . . . + ckS(n − k). Now, consider the linear system (with unknowns a1, . . . , an) a1r1 + a2r2 + . . . + akrk = S(1) a1r 2 1 + a2r 2 2 + . . . + akr 2 k = S(2) . . . a1r k 1 + a2r k 2 + . . . + akr k k = S(k). The coefficient matrix of the left hand side can be viewed as the product of a Vandermonde matrix and a diagonal matrix: r1 r2 . . . rk r 2 1 r 2 2 . . . r2 k . . . . . . r k 1 r k 2 . . . rk k = 1 1 . . . 1 r1 r2 . . . rk . . . . . . r k−1 1 r k−1 2 . . . rk−1 k r1 0 . . . 0 0 r2 . . . 0 . . . . . . 0 0 . . . rk . Consequently, the coefficient matrix must be full-rank, and the linear system must have a (unique) solution. When we use this solution as the constants in T0(n), we are guaranteed that T0(1) = S(1), T0(2) = S(2), . . . , T0(k) = S(k). A simple induction on n allows us to extend this result to T0(n) = S(n) for all positive integer n, because both T0() and S() satisfy the same recurrence. Example 2 A function T : Z + → Z+ satisfies the following conditions: • For all n1, n2 ∈ Z+ such that gcd(n1, n2) = 1, T(n1n2) = T(n1)T(n2). • For all m, n ∈ Z+ (n ≥ 2), T(mn ) = (T(mn−1 ))3 (T(mn−2))2 . Find the function T. 4
Solution:Consider an aay prime Since Tdefining()og),we get that S(n)=3S(n-1)-2S(n-2).The characteristic equation of this recurrence is x2-3x+2 =0,which has two distinct roots 1 and 2.Hence,the solution to this recurrence is S(n)=ap2n+bp,where ap,bp are constants. From T(1)T(n)=T(n),we easily get that T(1)=1.Hence S(0)=0,which means bp =-ap.Thus, S(n)=ap(2n-1),i.e.,T(p")=(2"-1)=(T(p))2"-1.For a general positive integer p"...where p1..&are primes,T(p)=(T(p))2-1...(T(pK))2-1.The value of T(p)for each prime p can be arbitrarily chosen from positive integers. Theorem 2 perfectly solves Equation(4)when the characteristic equation has distinct roots.But in reality,we often have double roots and triple roots.What can we do then?Fortunately,we have another theorem that takes care of multiple roots. Theorem 3 If Equations (5)has e roots r1,...,re,where ri is of multiplicity mi for i =1,...,e,then the solutions to Equation (4)are To(n) (a1+ai,2n+..+a,mnm-1)r, i=1 where aijs are all constants.There is no other solution to Equation (4). The proof of Theorem 3 is quite similar to that of Theorem 2.There are two major differences: Since ri is a root of multiplicity mi,on top of -g11-2-2-.-4=0, we also have kr5-1-a1(k-1)r-2-c2(k-2)r-3-.-ck-1=0, k(k-1)..(k-mi+2)r-m+1-c(k-1).(k-m+1)r-m-..ck-m+1(mi-11=0. These equations help us to show that To(n)satisfies the recurrence. A generalization of Vandermonde matrix is confluent Vandermonde matrix [12],which is also full-rank. Theorems 2 and 3 tell us how to solve homogeneous equations.To get the total solution of Equation(2), we still need find a particular solution.The bad news is that we do not have a systematic approach of finding a particular solution.The best we can do is only slightly better than the guess-and-prove method:the method of undetermined coefficients.It is slightly better in that we only need to guess what kind of function could be a particular solution,not the parameters of the function.As long as our guess is correct,the method of undertermined coefficients can help us correctly calculate the parameters of the function.Below we demonstrate how the method undetermined coefficients works. Example 3 Solve the recurrence nm=雪a-+营ra-g+-告m+号+
Solution: Consider an arbitrary prime p. Since T(p n ) = (T(p n−1 ))3 (T(pn−2))2 , defining S(n) = log T(p n ), we get that S(n) = 3S(n − 1) − 2S(n − 2). The characteristic equation of this recurrence is x 2 − 3x + 2 = 0, which has two distinct roots 1 and 2. Hence, the solution to this recurrence is S(n) = ap2 n + bp, where ap, bp are constants. From T(1)T(n) = T(n), we easily get that T(1) = 1. Hence S(0) = 0, which means bp = −ap. Thus, S(n) = ap(2n − 1), i.e., T(p n ) = 2ap(2n−1) = (T(p))2 n−1 . For a general positive integer p n1 1 . . . p nk k where p1, . . . , pk are primes, T(p n1 1 . . . p nk k ) = (T(p1))2 n1−1 . . .(T(pk))2 nk −1 . The value of T(p) for each prime p can be arbitrarily chosen from positive integers. Theorem 2 perfectly solves Equation (4) when the characteristic equation has distinct roots. But in reality, we often have double roots and triple roots. What can we do then? Fortunately, we have another theorem that takes care of multiple roots. Theorem 3 If Equations (5) has ` roots r1, . . . , r` , where ri is of multiplicity mi for i = 1, . . . , `, then the solutions to Equation (4) are T0(n) = X ` i=1 (ai,1 + ai,2n + . . . + ai,min mi−1 )r n i , where aij s are all constants. There is no other solution to Equation (4). The proof of Theorem 3 is quite similar to that of Theorem 2. There are two major differences: • Since ri is a root of multiplicity mi , on top of r k i − c1r k−1 i − c2r k−2 i − . . . − ck = 0, we also have krk−1 i − c1(k − 1)r k−2 i − c2(k − 2)r k−3 i − . . . − ck−1 = 0, . . . k(k − 1). . .(k − mi + 2)r k−mi+1 i − c1(k − 1). . .(k − mi + 1)r k−mi i − . . . ck−mi+1(mi − 1)! = 0. These equations help us to show that T0(n) satisfies the recurrence. • A generalization of Vandermonde matrix is confluent Vandermonde matrix [12], which is also full-rank. Theorems 2 and 3 tell us how to solve homogeneous equations. To get the total solution of Equation (2), we still need find a particular solution. The bad news is that we do not have a systematic approach of finding a particular solution. The best we can do is only slightly better than the guess-and-prove method: the method of undetermined coefficients. It is slightly better in that we only need to guess what kind of function could be a particular solution, not the parameters of the function. As long as our guess is correct, the method of undertermined coefficients can help us correctly calculate the parameters of the function. Below we demonstrate how the method undetermined coefficients works. Example 3 Solve the recurrence T(n) = e 3 2 T(n − 1) + e 6 2 T(n − 2) + (1 − e 3 + e 6 2 )en + e 4 2 + e 7 . 5
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=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. 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
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. P
Solution: 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
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) 9
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 complicated 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
Problem 4 (Example 10.14 of [10])Solve the recurrence system fT(n)=3T(n-1)+2S(n-1) S(n)=T(n-1)+S(n-1). Problem 5 (Optional,Bonus Question,USA TSTST 2017-6)A sequence fan}is said to be Fibonacci type if it satisfies the recurrence an =an-+an-2.Does there exist a partition P of positive integers,such that P is infinite,and that for all S E P,the elements of S can form a Fibonacci type sequence?Prove your answer. 4 The Annihilator Method Recall that an operator or functional means a high-order function that maps a function to another function.If we keep this definition in mind,we can see that a recurrence is actually a functional equation,in the sense that the unknown in a recurrence is a function.For example,the recurrence T(n)=T(n-1)+2T(n-2)-en can be understood in the following way:We take a function T(n),and apply an operator to map it to another function S(n)=T(n-1)+2T(n-2)-e";if we want the result S(n)to be equal to T(n)itself,what kind of function T(n)should we begin with? At the first look,this change of view does not seem to give us an immediate solution of the recurrence.We might even wonder what is the advantage of changing our view this way.However,if you have studied differential equations,you may remember that a similar change of view enables us to solve some differential equations.For differential equations,it is called"the annihilator method."Fortunately,the same method applies to recurrences as well. The main idea of this method is that we can always rewrite a recurrence in the form A(T(n)=0, where A is an operator.Since the operator A maps function T(n)to constant zero,it is called an annihilator of T(n).If we are lucky enough to know what operator annihilates what functions,then we can figure out function T(n)from its annihilator A. We are particularly interested in an operator L,which is the shiftting operator:For all function T(n)de- fined on natural numbers,IT(n)=T(n +1).In addition to L,we also consider another basic operator c,the multiplication-by-constant operator,which does nothing but multiplying a function by a constant c.Based on these two basic operators,we establish a family of operators using the following operations: .Addition.We can add two operators together to get another operator:for operators A1,A2,for all function T defined on natural numbers,(AI+A2)TeAT+A2T. Multiplication by constant.We can multiply an operator by a constant:for operator A,constant c,for all function T defined on natural numbers,(cA)T=(Ac)T def c(AT). 10
Problem 4 (Example 10.14 of [10]) Solve the recurrence system T(n) = 3T(n − 1) + 2S(n − 1) S(n) = T(n − 1) + S(n − 1). Problem 5 (Optional, Bonus Question, USA TSTST 2017-6) A sequence {an} is said to be Fibonacci type if it satisfies the recurrence an = an−1 + an−2. Does there exist a partition P of positive integers, such that P is infinite, and that for all S ∈ P, the elements of S can form a Fibonacci type sequence? Prove your answer. 4 The Annihilator Method Recall that an operator or functional means a high-order function that maps a function to another function. If we keep this definition in mind, we can see that a recurrence is actually a functional equation, in the sense that the unknown in a recurrence is a function. For example, the recurrence T(n) = T(n − 1) + 2T(n − 2) − e n can be understood in the following way: We take a function T(n), and apply an operator to map it to another function S(n) = T(n − 1) + 2T(n − 2) − e n ; if we want the result S(n) to be equal to T(n) itself, what kind of function T(n) should we begin with? At the first look, this change of view does not seem to give us an immediate solution of the recurrence. We might even wonder what is the advantage of changing our view this way. However, if you have studied differential equations, you may remember that a similar change of view enables us to solve some differential equations. For differential equations, it is called “the annihilator method.” Fortunately, the same method applies to recurrences as well. The main idea of this method is that we can always rewrite a recurrence in the form A(T(n)) = 0, where A is an operator. Since the operator A maps function T(n) to constant zero, it is called an annihilator of T(n). If we are lucky enough to know what operator annihilates what functions, then we can figure out function T(n) from its annihilator A. We are particularly interested in an operator L, which is the shiftting operator: For all function T(n) de- fined on natural numbers, LT(n) = T(n + 1). In addition to L, we also consider another basic operator c, the multiplication-by-constant operator, which does nothing but multiplying a function by a constant c. Based on these two basic operators, we establish a family of operators using the following operations: • Addition. We can add two operators together to get another operator: for operators A1, A2, for all function T defined on natural numbers, (A1 + A2)T def = A1T + A2T. • Multiplication by constant. We can multiply an operator by a constant: for operator A, constant c, for all function T defined on natural numbers, (cA)T = (Ac)T def = c(AT). 10
