Changing a Recurrence Relation into a General Formula

Date: 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/