《Mathematics for Computer》Notes for Recitation 12

6.042/18.] Mathematics for Computer Science March 18 2005 Srini devadas and Eric Lehman Notes for recitation 12 1 Solving linear recurrences Guessing a particular solution. Recall that a general linear recurrence has the form f(n)=a1f(n-1)+a2f(n-2)+…+aaf(n-d)+g(n) As explained in lecture, one step in solving this recurrence is finding a particular solu tion; i.e., a function f(n) that satisfies the recurrence, but may not be consistent with the boundary conditions. Here's a recipe to help you guess a particular solution If g(n) is a constant, guess that f(n) is some constant c Plug this into the recurrence and see if any constant actually works. If not, try f(n)= bn+c, then f(n)=an2+ + ete More generally, if g(n) is a polynomial, try a polynomial of the same degree. If that fails, try a polynomial of degree one higher, then two higher, etc. For example, if g(n)=n, then try f(n)=bn +c and then f(n)=an+bn+c If g(n)is an exponential, such as 3 n, then first guess that f(n)=c3n. Failing that, try f(n)=bn3n+c3n and then an 3n+ bn3n+c3n,etc In practice, your first or second guess will almost always work. Dealing with repeated roots. In lecture we saw that the solutions to a linear recurrence are determined by the roots of the characteristic equation: For each root r of the equation, the function rn is a solution to the recurrence Taking a linear combination of these solutions, we can move on to find the coefficients The situation is a little more complicated when r is a repeated root of the characteristic equation: if its multiplicity is k, then(not only rn, but) each of the functions mrn nrl a solution to the recurrence o that our linear combination must use all of them

6.042/18.062J Mathematics for Computer Science March 18, 2005 Srini Devadas and Eric Lehman Notes for Recitation 12 1 Solving linear recurrences Guessing a particular solution. Recall that a general linear recurrence has the form: f(n) = a1f(n − 1) + a2f(n − 2) + · · · + adf(n − d) + g(n) As explained in lecture, one step in solving this recurrence is finding a particular solu￾tion; i.e., a function f(n) that satisfies the recurrence, but may not be consistent with the boundary conditions. Here’s a recipe to help you guess a particular solution: • If g(n) is a constant, guess that f(n) is some constant c. Plug this into the recurrence and see if any constant actually works. If not, try f(n) = bn + c, then f(n) = an2 + bn + c, etc. • More generally, if g(n) is a polynomial, try a polynomial of the same degree. If that fails, try a polynomial of degree one higher, then two higher, etc. For example, if 2 g(n) = n, then try f(n) = bn + c and then f(n) = an + bn + c. • If g(n) is an exponential, such as 3n, then first guess that f(n) = c3n. Failing that, try f(n) = bn3n + c3n and then an23n + bn3n + c3n, etc. In practice, your first or second guess will almost always work. Dealing with repeated roots. In lecture we saw that the solutions to a linear recurrence are determined by the roots of the characteristic equation: For each root r of the equation, the function rn is a solution to the recurrence. Taking a linear combination of these solutions, we can move on to find the coefficients. The situation is a little more complicated when r is a repeated root of the characteristic equation: if its multiplicity is k, then (not only rn, but) n n 2 n each of the functions r , nr , n r , . . . , nk−1rn is a solution to the recurrence, so that our linear combination must use all of them

Recitation 12 2 Mini-Tetris(again) Remember Mini-Tetris from Recitation 4? Here is an overview: A winning configuration in the game is a complete tiling of a 2 x n board using only the three shapes shown below For example, the several possible winning configurations on a 2 x 5 board include In that past recitation, we had defined Tn to be the number of different winning config urations on a 2 x n board. Then we had to inductively prove Tn equals some particular closed form expression Remember that expression? Probably not. But no damage, now you can find it on your own (a) determine the values of T1, 12, and T3 Solution T1=l, T2=3, and T3=5. (b) Find a recurrence equation that expresses Tn in terms of Tn-I and Tn-2 Solution. Every winning configuration on a 2 X n board is of one three types, dis- tinguished by the arrangment of pieces at the top of the board There are Tn-1 winning configurations of the first type, and there are Tn-2 winning configurations of each of the second and third types. Overall, the number of win ning configurations on a 2 X n board is Tn=Tn-1+21n-2

Recitation 12 2 2 Mini­Tetris (again) Remember Mini­Tetris from Recitation 4? Here is an overview: A winning configuration in the game is a complete tiling of a 2 × n board using only the three shapes shown below: For example, the several possible winning configurations on a 2 × 5 board include: In that past recitation, we had defined Tn to be the number of different winning config￾urations on a 2 × n board. Then we had to inductively prove Tn equals some particular closed form expression. Remember that expression? Probably not. But no damage, now you can find it on your own. (a) Determine the values of T1, T2, and T3. Solution. T1 = 1, T2 = 3, and T3 = 5. (b) Find a recurrence equation that expresses Tn in terms of Tn−1 and Tn−2. Solution. Every winning configuration on a 2 × n board is of one three types, dis￾tinguished by the arrangment of pieces at the top of the board. n − 1 n − 2 n − 2 There are Tn−1 winning configurations of the first type, and there are Tn−2 winning configurations of each of the second and third types. Overall, the number of win￾ning configurations on a 2 × n board is: Tn = Tn−1 + 2Tn−2

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 (*)

Recitation 12 (c) The complete solution to the recurrence is the homogenous solution plus the partic- ular solution Use the initial conditions to find the coefficients Solution 2 All that remains is to find the constants A and B. Substituting the initial conditions gives a system of linear equations A+B-1 +√5 B The solution to this linear system is 5+3√5 10 5-3√5 10 (d) Therefore, the complete solution to the recurrence is Solution 35)/1+√5 T 4 Back to homogeneous ones Let's get back to homogeneous linear recurrences. Find a closed-form solution to this one So=0 S1=1 9S Anything strange? Solution. The characteristic polynomial is r2-6r+9=(r-3)2, so we have a repeated root: r=3, with multiplicity 2. The solution is of the form A3"+ Bn3" for some constants a and e. Setting n=0, we have0=S=43°+B.0·3°=A. Setting n=1, we have 1=S1=A31+B·1.31=3B,soB=1/3. That is

Recitation 12 4 (c) The complete solution to the recurrence is the homogenous solution plus the partic￾ular solution. Use the initial conditions to find the coefficients. Solution. � � 1 − √5 n �n 1 + √5 � Tn = A + B − 1 2 2 All that remains is to find the constants A and B. Substituting the initial conditions gives a system of linear equations. 0 = A + B − 1 � � 1 − √5 � 1 + √5 � 1 = A + B − 1 2 2 The solution to this linear system is: 5 + 3√5 A = 10 5 − 3 √5 B = 10 (d) Therefore, the complete solution to the recurrence is: Solution. � � �5 − 3 √5 � �1 − √5 n �n 5 + 3√5 � �1 + √5 Tn = + − 1. 10 · 2 10 · 2 4 Back to homogeneous ones Let’s get back to homogeneous linear recurrences. Find a closed­form solution to this one. S0 = 0 S1 = 1 Sn = 6Sn−1 − 9Sn−2 Anything strange? 2 Solution. The characteristic polynomial is r − 6r + 9 = (r − 3)2, so we have a repeated root: r = 3, with multiplicity 2. The solution is of the form A3n + Bn3n for some constants A and B. Setting n = 0, we have 0 = S0 = A30 + B · 3 0 · 0 = A. Setting n = 1, we have 1 = S1 = A31 + B · 3 1 · 1 = 3B, so B = 1/3. That is, 1 n3n Sn = 0 · 3n + = n3n−1 . 3 ·

Recitation 12 5 Short Guide to Solving Linear recurrences A linear recurrence is an equation f(n)=alf(n-1)+a2f(n-2)+.+adf(n-d) +g(n) homogeneous part together with boundary conditions such as f(0)=bo, f(1)=b1,etc 1. Find the roots of the characteristic equation 2. Write down the homogeneous solution. Each root generates one term and the homoge- neous solution is the sum of these terms. A nonrepeated root r generates the term crrn where cr is a constant to be determined later. A root r with multiplicity k generates the terms. where cru, .. C are constants to be determined later. 3. Find a particular solution. This is a solution to the full recurrence that need not be con sistent with the boundary conditions. Use guess and verify. If g(n) is a polynomial, try a polynomial of the same degree, then a polynomial of degree one higher, then two higher, etc. For example, if g(n)=n, then try f(n)=bn+ and then f(n)=an+bn+c If g()is an exponential, such as 3", then first guess that f(n)=c3". Failing that, tr f(n)=bn3"+c3" and then ann+bm3n+c3",etc 4. Form the general solution, which is the sum of the homogeneous solution and the partic ular solution. Here is a typical general solution f(m)=c2n+d(-1) homogeneous solution particular solution 5. Substitute the boundary conditions into the general solution. Each boundary condition gives a linear equation in the unknown constants. For example, substituting f(1)=2 into the general solution above gives 2+d·(-1)2+3.1 d Determine the values of these constants by solving the resulting system of linear equa

Recitation 12 5 Short Guide to Solving Linear Recurrences A linear recurrence is an equation f(n) = a1f(n − 1) + a2f(n − 2) + . . . + adf(n − d) +g(n) � �� � � �� � homogeneous part inhomogeneous part together with boundary conditions such as f(0) = b0, f(1) = b1, etc. 1. Find the roots of the characteristic equation: nx = a1xn−1 + a2xn−2 + . . . + ak 2. Write down the homogeneous solution. Each root generates one term and the homoge­n neous solution is the sum of these terms. A nonrepeated root r generates the term crr , where cr is a constant to be determined later. A root r with multiplicity k generates the terms: n n 2 n n cr1 r , cr2 nr , cr3 n r , . . . , crk nk−1r where cr1 , . . . , cr are constants to be determined later. k 3. Find a particular solution. This is a solution to the full recurrence that need not be con￾sistent with the boundary conditions. Use guess and verify. If g(n) is a polynomial, try a polynomial of the same degree, then a polynomial of degree one higher, then two higher, etc. For example, if g(n) = n, then try f(n) = bn+c and then f(n) = an2+bn+c. If g(n) is an exponential, such as 3n, then first guess that f(n) = c3n. Failing that, try f(n) = bn3n + c3n and then an23n + bn3n + c3n, etc. 4. Form the general solution, which is the sum of the homogeneous solution and the partic￾ular solution. Here is a typical general solution: n f(n) = c2 + n + d(−1) 3n + 1 � �� � � �� � homogeneous solution particular solution 5. Substitute the boundary conditions into the general solution. Each boundary condition gives a linear equation in the unknown constants. For example, substituting f(1) = 2 into the general solution above gives: 2 = c · 21 + d · (−1)1 + 3 · 1 + 1 ⇒ −2 = 2c − d Determine the values of these constants by solving the resulting system of linear equa￾tions