Second-Order Linear RecurrencesDate: 06/08/2001 at 11:51:25 From: Lanada M. Jones Subject: Discrete Math/Recurrence relation Hi, I was wondering if I could get help with the following problems: 1. Find a recurrence relation for the number of bit strings of length n that do not contain a pair of consecutive zeroes. What are the initial conditions? 2. Solve the following recurrence relations together with the inital conditions given: a n = 4 a n-1 - 4 a n-2; a0 = 6 a1 = 8 In other words, a sub n = 4 times a sub n minus 1 minus 4 times a sub n minus 2; a sub zero equals six, a sub one equals eight. 3. Consider the sequence 0, 1, 1/2, 3/4, 5/8, 11/16, ..., in which each term is the average of the previous two terms (eg., the next term will be 1/2(5/8 + 11/16) = 21/32. Find the formula for the general term using a recurrence equation. Make sure you state the inital condition. Then give a formula for the general term using a non-recursive equation by solving the above recurrence equation. I would appreciate any help you can give to help me get started with these problems. Date: 06/08/2001 at 13:08:00 From: Doctor Rob Subject: Re: Discrete Math/Recurrence relation Thanks for writing to Ask Dr. Math, Lanada. Here are the steps to solving second-order linear recurrences. 1. Find the recurrence relations and initial conditions. In the first problem, it is given. In the second, you have to find it: a(n) = [a(n-1)+a(n-2)]/2, a(0) = 0, a(1) = 1. 2. Write it in the form a(n) + c(1)*a(n-1) + c(2)*a(n-2) = 0, where c(1) and c(2) are constants. 3. Write down the characteristic polynomial x^2 + c(1)*x + c(2). 4. Find the roots of this polynomial. They can be r(1) and r(2), distinct roots, or r(1), a double root. 5. Write down the general solution of the recurrence. In the case of distinct roots, that is a(n) = k(1)*r(1)^n + k(2)*r(2)^n. In the case of a double root, that is a(n) = [k(1)*n + k(2)]*r(1)^n. Here k(1) and k(2) are two arbitrary constants. 6. Use the initial conditions to set up equations in the unknown constants k(1) and k(2). 7. Solve those simultaneous linear equations and find the values of k(1) and k(2). 8. Write the explicit solution of the recurrence satisfying the initial conditions. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 06/09/2001 at 05:19:01 From: Doctor Anthony Subject: Re: Discrete Math/Recurrence relation >1. Find a recurrence relation for the number of bit strings of length n that do not contain a pair of consecutive zeroes. What are the initial conditions? Let u(n) be the number of strings of length n that DO NOT contain consecutive 0's. Let u(n0) = number of strings that start with 0 u(n1) = number of strings that start with 1 Then u(n) = u(n0) + u(n1) If the first number in the string is 1 then the string can be completed in u(n-1) ways. So u(n1) = u(n-1). If the first number in the string is 0, then the second number must be 1. So u(n0) = u((n-1)1) = u(n-2) Therefore u(n) = u(n0) + u(n1) becomes u(n) = u(n-2) + u(n-1) Note that this is the recurrence relation for the number of strings that DO NOT have consecutive 0's. This is the familiar recurrence relation for the Fibonacci series. >2. Solve the following recurrence relations together with the inital conditions given: a n = 4 a n-1 - 4 a n-2; a0 = 6 a1 = 8 a(n) = 4.a(n-1) - 4.a(n-2) a(n) - 4.a(n-1) + 4.a(n-2) = 0 The auxiliary equation is x^2 - 4x + 4 = 0 (x-2)^2 = 0 With the double root the solution is a(n) = (A + B.n)2^n a0 = 6, a1 = 8 6 = A 8 = (6 + B)2 so B+6 = 4 and B = -2 Therefore a(n) = (6 - 2n)2^n >3. Consider the sequence 0, 1, 1/2, 3/4, 5/8, 11/16, ..., in which each term is the average of the previous two terms (eg., the next term will be 1/2(5/8 + 11/16) = 21/32. Find the formula for the general term using a recurrence equation. Make sure you state the inital condition. Then give a formula for the general term using a non-recursive equation by solving the above recurrence equation. u(n) = (1/2)[u(n-1) + u(n-2)] 2.u(n) - u(n-1) - u(n-2) = 0 The auxiliary equation is 2x^2 - x - 1 = 0 (2x+1)(x-1) = 0 x=1 or x = -1/2 So u(n) = A + B(-1/2)^n 0 = A + B so A = -B 1 = A - B/2 1 = -B - B/2 1 = -3B/2 therefore B = -2/3 then A = 2/3 u(n) = 2/3 - (2/3)(-1/2)^n check: u(5) = (2/3)[1 - (-1/2)^5] = (2/3)[1 + 1/32] = (2/3)[33/32] = 11/16 which is correct. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Ask Dr. MathTM
© 1994-2002 The Math Forum
http://mathforum.org/dr.math/