Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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
teacher to give you such an equation.

-Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search