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