Originally Posted by

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

__The recurrence relation is__:

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

Which means that:

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

__Solving this gives the answer__:

$\displaystyle 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:

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

*- where $\displaystyle \epsilon \approx$ 10^-17*

But this expression for $\displaystyle 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 $\displaystyle x_n$ incorrect?