Changing a Recurrence Relation into a General FormulaDate: 03/06/98 at 14:04:12 From: Edwin Wollacott Subject: solving a recurrence relation (linked with Fibonacci) I have been set this task by my teacher: change into a general formula the recurrence relation An = an_1 + an_3 I know that the Fibonacci sequence is An = an_1 + an_2 and its general formula is An = 1/sqrt5({1/2[1 + sqrt5]}^n - {1/2[1 - sqrt5]}^n} They seem very similar, but I don't know how to go about it. Please help me! I have been trying to find a site as superb as yours for days, but unfortunately, my deadline is Monday. Once again, please help me, as I am desperate. Date: 03/06/98 at 16:05:41 From: Doctor Rob Subject: Re: solving a recurrence relation (linked with Fibonacci) In the Fibonacci sequence, the numbers (1 + sqrt[5])/2 and (1 - sqrt[5])/2 are the roots of the equation x^2 = x + 1. In your sequence, you will need to use instead the roots of the equation x^3 = x + 1. These are harder to find, especially since one is real but the other two are complex! If you call them a, b, and c, then the formula you seek will have the form A(n) = k1*a^n + k2*b^n + k3*c^n, where k1, k2, and k3 are constants determined by the initial values of A(0), A(1), and A(2). These you can find by substituting in n = 0, 1, and 2 in the formula, using the known values of A(0), A(1), and A(2), and solving the system of linear equations for k1, k2, and k3. You can probably use the facts that a + b + c = 0, a*b + a*c + b*c = -1, a*b*c = -1, and a^2 + b^2 + c^2 = 2. You can check that k1*a^n is a solution of the recursion, as is k2*b^n and k3*c^n, for any k1, k2, and k3. You will have to use the fact that a, b, and c are solutions of x^3 - x - 1 = 0. The general rule is that a solution of such recurrences has the form A(n) = k*a^n. Here, k is some constant, the value of which is arbitrary. The value of the variable a can be determined by substituting this form into the recursion and solving for the value of a. Actually, there will be three values of a that work, one real and two complex(!). That means that the general solution will be a sum of terms of the above form, one for each value of a, with possibly different constants k. A(n) = k1*a1^n + k2*a2^n + k3*a3^n, where n >= 0. The values of the constants k are determined by the fact that when n = 0, 1, and 2, you get the equations A(0) = k1 + k2 + k3, A(1) = k1*a1 + k2*a2 + k3*a3, A(2) = k1*a1^2 + k2*a2^2 + k3*a3^2. You should know these initial values of A(n), and so be able to solve the resulting system of linear equations for k1, k2, and k3. -Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 03/06/98 at 16:45:01 From: Doctor Anthony Subject: Re: solving a recurrence relation (linked with Fibonacci) The general method is to write the difference equation in the form: u(n+3) - u(n+2) - u(n) = 0 (E^3 - E^2 - 1)u(n) = 0 If the roots of m^3 - m^2 - 1 = 0 are a, b, c, then u(n) = A*a^n + B*b^n + C*c^n where A, B, C are constants. You will need the first three terms of the series to fix the values of A, B and C. In fact, the equation m^3 - m^2 - 1 = 0 has one real and two complex roots. The real root is 1.46557. If you divide by (m - 1.46557), you obtain a quadratic giving two conjugate complex roots. If these are of the form r*e^(i*theta) then u(n) = A*1.46557^n + B*r^n(cos(n*theta) + i*sin(n*theta)) + C*r^n(cos(n*theta) - i*sin(n*theta)) As you can see, there is no nice simple expression for the nth term of the series. To get a neat solution, you require the m equation to have easy factors like (m-2)(m-3)(m-5). Perhaps you can persuade your teacher to give you such an equation. -Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/