Report

Homogeneous Linear Recurrences To solve such recurrences we must first know how to solve an easier type of recurrence relation: DEF: A linear recurrence relation is said to be homogeneous if it is a linear combination of the previous terms of the recurrence without an additional function of n or a constant. an = 2an-1 is homogeneous an = 2an-1 + 2n-3 - an-3 is not. bk = 2bk-1 - bk-2 + 4bk-3 + 2 is not. Homogeneous Linear Recurrences To solve such recurrences we must first know how to solve an easier type of recurrence relation: DEF: A linear recurrence relation is said to be homogeneous if it is a linear combination of the previous terms of the recurrence without an additional function of n or a constant. an = 2an-1 is homogeneous an = 2an-1 + 2n-3 - an-3 is not. bk = 2bk-1 - bk-2 + 4bk-3 + 2 is not. First Order Homogenous Recurrences Quiz tomorrow from Solving Recurrence Relations b0 2 bk 3bk 1k 0 Characteristic equation D3 General Solution: bk A(root 1) k bk A(3) k Using initial conditions: b0 A(3) 0 2 A Closed Form Solution: bk 2(3) k 2 6 18 54 162 486 1458 4374 0 1 2 3 4 5 6 7 2 6 18 54 162 486 1458 4374 Solving Homogenous Recurrences Finding a closed form solution to a recurrence relation. Multiply both sides by a0 1 r n 2 a1 8 r n 2 r n r n 2 r n1 2r n 2 r n2 0 an an 1 2an 2n 2 r n 2 n r n 2 n1 2r n 2 n2 0 an an 1 2an 2 Let an r n r n r n 1 2r n 2 r n r n 1 2r n 2 0 r 2 r 2 0 Characteristic equation r 2 2r r 2 0 r (r 2) (r 2) 0 (r 2)(r 1) 0 r2 roots r 1 Example continued… The closed form solution is given by: Let an A(root1) n B(root2) n an A(2) n B(1) n be the solution. 1 Where constants A and B are to determined by employing initial conditions. a0 1, a1 8 Plug in n = 0 in equation 1 to obtain: a0 A(2)0 B(1)0 1 A B Plug in n = 1 in equation 1 to obtain: a1 A(2)1 B(1)1 8 2 A B Adding the two equation, we get A B 1 2A B 8 3A 9 A 3, B 2 Example continued… By substituting A = 3 and B = -2 in equation 1, we get the final solution in the closed form: an 3(2) 2(1) n Verification an 3(2) n 2(1) n Test Data a0 3(2) 0 2(1) 0 a0 1 a0 3 2 1 a1 3(2) 2(1) 1 1 a1 3(2) 2(1) 6 2 8 a2 3(2) 2(1) 3 * 4 2 *1 2 2 12 2 10 a3 3(2) 3 2(1) 3 24 2 26 a4 3(2) 4 2(1) 4 48 2 46 a5 3(2) 5 2(1) 5 96 2 98 a1 8 a2 10 a3 26 a4 46 a5 98 n Example 2 b0 2 b1 2 bk 7bk 1 10bk 2k 2 D 2 7 D 10 D 2 7 D 10 0 ( D 2)(D 5) 0 D 2, D 5 The closed form solution is given by: bk A(root1) k B(root2) k bk A(2) k B(5) k Using initial conditions: bk A(2) k B(5) k b0 A(2) 0 B(5) 0 2 A B b1 A(2)1 B(5)1 2 2 A 5B 2 A B 2 2 A 5B 2 8 B ,A 3 3 8 2 bk (2) k (5) k 3 3 Solution of Fibonacci Recurrence a0 1 a1 1 an an1 an2n 2 Solve the quadratic equation: r 2= r + 1 r 2 - r - 1 = 0 Characteristic equation to obtain r1 = (1+5)/2 r2 = (1-5)/2 General solution: an = A [(1+5)/2]n +B [(1-5)/2]n Fibonacci Recurrence Use initial conditions a0 = 0, a1 = 1 to find A,B and obtain specific solution. 0=a0 = A [(1+5)/2]0 +B [(1-5)/2]0 = A +B That is A +B = 0 --- (1) 1=a1 = A [(1+5)/2]1 +B [(1-5)/2]1 = A(1+5)/2 +B (1-5)/2 = (A+B )/2 + (A-B )5/2 That is (A+B )/2 + (A-B )5/2 = 1 or (A+B ) + (A-B )5 = 2 -- (2) First equation give B = -A. Plug into 2nd: A = 1/5, B = -1/5 n Final answer: 1 1 5 an 5 2 1 1 5 2 5 n Case where the roots are identical Finding a closed form solution to a recurrence relation when the roots are identical. t0 1 t1 3 tk 6tk 1 9tk 2k 2 D 6D 9 2 D 2 6D 9 0 ( D 3) 2 0 D3 Test Data The closed form solution is given by: t k A( root 1) k Bk ( root 2) k t k A(3) k Bk (3) k t0 1 t1 3 t2 9 t3 27 t 4 81 t5 243 t6 729 Where constants A and B are to determined by employing initial conditions. t k A(3) k Bk (3) k t0 1 I t1 3 Plug in k = 0 in equation 1 to obtain: Plug in k= 1 in equation 1 to obtain: t0 A(3) 0 B * 0 * (3)0 1 A A 1. t1 A(3)1 B *1* (3)1 3 3 A 3B A B 1 A 1 B0 tk (3) k A variation of the previous Example Finding a closed form solution to a recurrence relation when the roots are identical. t0 0 t1 3 tk 6tk 1 9tk 2k 2 D 6D 9 2 D 2 6D 9 0 ( D 3) 2 0 D3 Test Data The closed form solution is given by: t k A( root 1) k Bk ( root 2) k t k A(3) k Bk (3) k t0 0 t1 3 t 2 18 t3 81 t 4 324 Where constants A and B are to determined by employing initial conditions. t k A(3) k Bk (3) k t0 0 t0 0 t1 3 I t 2 18 t1 3 t3 81 t 4 324 Plug in k = 0 in equation 1 to obtain: Plug in k= 1 in equation 1 to obtain: t0 A(3) 0 B * 0 * (3) 0 0 A A 0. t1 A(3)1 B *1* (3)1 3 3 A 3B A B 1 A0 B 1 tk k (3) k Relationship between Recurrence Relation and Sequences Finding sequences that satisfy a recurrence relation. bk 7bk 1 10bk 2k 2 Characteristic equation D 2 7 D 10 b0, b1, b2, …. D 7 D 10 0 ( D 2)(D 5) 0 D 2, D 5 2 1, 2, 4, 8, The given recurrence is satisfied by the following sequences: Or … 1, 5, 25, 125, 1, (2)1, (2)2, (2)3 , … 1, (5)1, (5)2, (5)3 , … … Verification bk 7bk 1 10bk 2k 2 1, 2, 4, 8, … b2 7b1 10b0 b2 7 * 2 10*1 4 b3 7b2 10b1 7 * 4 10* 2 28 20 8 1, 5, 25, 125, … b2 7b1 10b0 b2 7 * 5 10*1 25 b3 7b2 10b1 7 * 25 10* 5 175 50 125 Practice Problem a0 2 a1 3 a k 3a k 1 2a k 2 k 2 List first 5 terms of sequence generated by the recurrence. Solve the recurrence in the close form. Step 1: Write characteristic equation. Step 2: Find roots of the characteristic equation. Step 3: Write the general solution. ak A(root1) k B(root2) k Step 4: Find constants A and B using boundary conditions. Step 5: Substitute constants in the general solution. Solving Recurrences using Spreadsheet a0 2 a1 3 a k 3a k 1 2a k 2 k 2 2 3 5 9 17 33 65 129 257 513 2 3 =3*A2-2*A1 =3*A3-2*A2 =3*A4-2*A3 =3*A5-2*A4 =3*A6-2*A5 =3*A7-2*A6 =3*A8-2*A7 =3*A9-2*A8 3rd order Homogenous Recurrences a 0 2, Where A, B, and C are constants to be determined by using boundary conditions. Let r = 0 a1 1, a2 1 ar 6ar 1 11ar 2 6ar 3 Characteristic equation a0 A(1) 0 B(2) 0 C (3) 0 D 3 6D 2 11D 6 2 A B C A B C 2 D 6D 11D 6 0 3 2 Roots D = 1, D = 2, and D = 3 General Solution: ar A(1) B(2) C(3) r r r (I) Let r = 1 a1 A(1)1 B(2)1 C (3)1 1 A 2 B 3C A 2 B 3C 1 (II) 3rd order Homogenous Recurrences Let r = 2 The solution is not complete. a 2 A(1) 2 B(2) 2 C (3) 2 1 A 4 B 9C A 4 B 9C 1 (III) We have to solve (I), (II), and (III) simultaneously for A, B, and C. A BC 2 A 2 B 3C 1 A 4 B 9C 1