Recitation 12 (c)Find a closed-form expression for T, Solution. The characteristic polynomial isr2-r-2=(r-2)(r+1), so the solution is of the form A2n+ B(1)". Setting n= l, we have 1= T1=2A-B Setting n=2, we have 3= T2=A22+B(1)2=4.A+B Solving these two equations, we conclude A= 2/3 and B=1/ 3. That is, the closed form expression for Tn is Remember it now? 3 Inhomogeneous linear recurrences Find a closed- form solution to the following linear recurrence Tn=In-1+In-2+1 (a) First find the general solution to the corresponding homogenous recurrence Solution. The characteristic equation is r2-r-1=0. The roots of this equation are Therefore, the solution to the homogenous recurrence is of the form 1+√ T=A +B (b) Now find a particular solution to the inhomogenous recurrence Solution. Since the inhomogenous term is constant, we guess a constant solution, c So replacing the T terms in ()by c, we require C=c+c+1, amely, c=-1. That is, Tn=-1 is a particular solution to()Recitation 12 3 (c) Find a closed­form expression for Tn. Solution. The characteristic polynomial is r2 −r −2 = (r −2)(r + 1), so the solution n is of the form A2n + B(−1) . Setting n = 1, we have 1 = T1 = 2A − B. Setting 2 n = 2, we have 3 = T2 = A22 + B(−1) = 4A + B. Solving these two equations, we conclude A = 2/3 and B = 1/3. That is, the closed form expression for Tn is n 2 1 Tn = 2n + (−1)n = 2n+1 + (−1) . 3 3 3 Remember it now? 3 Inhomogeneous linear recurrences Find a closed­form solution to the following linear recurrence. T0 = 0 T1 = 1 Tn = Tn−1 + Tn−2 + 1 (*) (a) First find the general solution to the corresponding homogenous recurrence. 2 Solution. The characteristic equation is r − r − 1 = 0. The roots of this equation are: 1 + √5 r1 = 2 1 − √5 r2 = 2 Therefore, the solution to the homogenous recurrence is of the form � � 1 − √5 n �n 1 + √5 � Tn = A + B . 2 2 (b) Now find a particular solution to the inhomogenous recurrence. Solution. Since the inhomogenous term is constant, we guess a constant solution, c. So replacing the T terms in (*) by c, we require c = c + c + 1, namely, c = −1. That is, Tn ≡ −1 is a particular solution to (*)