# Thread: Recurrence relations in Python

1. ## Recurrence relations in Python

I am trying to make a program in Python to find the solutions for for $x_n$ in a recurrence relation.

The recurrence relation is:

$x_{n+2} - 3x_{n+1} + x_{n} = 0$ with $x_{0} = 1, x_{1} = \frac{3-sqrt(5)}{2}$

Which means that:

$x_{n+2} = 3x_{n+1} - x_{n} = 0$

$x_{n} = (\frac{3-sqrt(5)}{2})^n$

The program I wrote was:

from math import *

N = 801

x = range(0,N)

x[0] = 1.0
x[1] = (3-sqrt(5))/2

for n in range(2,N):
x[n] = 3* x[n-1] - x[n-2]
print n, ': ', x[n]

It starts off good; with the values:
2 : 0.14589803375
3 : 0.0557280900008
4 : 0.0212862362522

but then, at n = 19 to n = 20, I get:
19 : 9.31783539215e-09
20 : -1.18877885313e-09

Why is this?
I calculated that the computer would run the program as if:

$x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)})(\frac{3-sqrt(5)}{2})^n$
- where $\epsilon \approx$ 10^-17

But this expression for $x_n$ should not have large negative values when n becomes large

So, didn't I write the program correctly? Or is the last expression for $x_n$ incorrect?

2. Originally Posted by jenkki
I am trying to make a program in Python to find the solutions for for $x_n$ in a recurrence relation.

The recurrence relation is:

$x_{n+2} - 3x_{n+1} + x_{n} = 0$ with $x_{0} = 1, x_{1} = \frac{3-sqrt(5)}{2}$

Which means that:

$x_{n+2} = 3x_{n+1} - x_{n} = 0$

$x_{n} = (\frac{3-sqrt(5)}{2})^n$

The program I wrote was:

from math import *

N = 801

x = range(0,N)

x[0] = 1.0
x[1] = (3-sqrt(5))/2

for n in range(2,N):
x[n] = 3* x[n-1] - x[n-2]
print n, ': ', x[n]

It starts off good; with the values:
2 : 0.14589803375
3 : 0.0557280900008
4 : 0.0212862362522

but then, at n = 19 to n = 20, I get:
19 : 9.31783539215e-09
20 : -1.18877885313e-09

Why is this?
I calculated that the computer would run the program as if:

$x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)})(\frac{3-sqrt(5)}{2})^n$
- where $\epsilon \approx$ 10^-17

But this expression for $x_n$ should not have large negative values when n becomes large

So, didn't I write the program correctly? Or is the last expression for $x_n$ incorrect?
It is the result of rounding errors

CB

3. Originally Posted by CaptainBlack
It is the result of rounding errors
Yes it is. What I don't understand is why I get large negative values instead of large positive values for large values of n.

When I used the fact the the computer looks at the start-value $x_1$ like it says: $x_1 = \frac{3-sqrt(5)}{2} + \epsilon$, where $\epsilon$ is the small error, I got this expression for $x_n$:

$x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)}))(\frac{3-sqrt(5)}{2})^n$

Which says that $x_n$ should take large positive values when n is a large number. But the Python-program I made says that the larger the n, the more negative $x_n$ becomes.

Therefore I suspect my program (see first post) is incorrect. I would really appriciate it if someone would help me what's wrong with it

4. Originally Posted by jenkki
Yes it is. What I don't understand is why I get large negative values instead of large positive values for large values of n.

When I used the fact the the computer looks at the start-value $x_1$ like it says: $x_1 = \frac{3-sqrt(5)}{2} + \epsilon$, where $\epsilon$ is the small error, I got this expression for $x_n$:

$x_{n} = (\frac{\epsilon}{sqrt(5)})(\frac{3+sqrt(5)}{2})^n + (1 -(\frac{\epsilon}{sqrt(5)}))(\frac{3-sqrt(5)}{2})^n$

Which says that $x_n$ should take large positive values when n is a large number. But the Python-program I made says that the larger the n, the more negative $x_n$ becomes.

Therefore I suspect my program (see first post) is incorrect. I would really appriciate it if someone would help me what's wrong with it
You have not got large values of any kind, negative powers of 10 are small numbers.

The sequence is decreasing so the small random errors in the initial stages can eventually dominate and the error will have an essentially random sign when it becomes dominant (it is actually deterministic but we don't know what it will be without an analysis of the floating point representation of the initial numbers and tracking the floating point errors as the accumulate through the iteration).

In fact since you know the analytic solution of the recurrence you can compare the results at each stage and see the error grow and eventually dominate.

If you continue the iteration beyond the point where the errors start to dominate you will get a sequence growing in absolute value. Since the iteration has a general solution with a growing term and a shrinking term and eventually the errors will drive the dominant growing term.

The initial conditions for the exact iteration force the selection of the decreasing term in the general solution of the recurrence, any error at any stage (and there are errors at all stages) will give free reign to the growing noise driven solution eventually.

(if you must focus only on the original error: your $\epsilon$ has a random sign)

CB