Solving linear recurrencesMini-Tetris (again)Inhomogeneous linear recurrencesBack to homogeneous ones6.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 ( + adf (n − d) + g(n)n − 2) + ···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 2g(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 neach 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 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 dama ge, 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−2Recitation 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 nis of the form A2n + B(−1) . Setting n = 1, we have 1 = T1 = 2A − B. Setting 2n = 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 n2 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. 2Solution. 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 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? 2Solution. 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 · 30 = A. Setting n = 1, we have 0 ·1 = S1 = A31 + B · 31 = 3B, so B = 1/3. That is, 1 ·1 n3nSn = 0 · 3n + = n3n−1 . 3 ·5 Recitation 12 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: n x = a1x n−1 + a2x n−2 + . . . + ak 2. Write down the homogeneous solution. Each root generates one term and the homoge-nneous solution is the sum of these terms. A nonrepeated root r generates …
View Full Document
Unlocking...