# What to expect when i simulate a recurrence relation?

• Sep 28th 2010, 11:21 AM
bjorno
What to expect when i simulate a recurrence relation?
I am working on an assignment, and I am having trouble with this recurrence relation:

x(n+2) - 3x(n+1) + x(n) = 0
x(0) = 1
x(1) = (3-sqrt(5))/2

What can you expect to happen when you simulate this equation numerically?

The next task is to simulate the equation in python, but for now, they want me to point out what kind of problems I might run into.
I figured that x(1) will not be represented correctly when converted to a 64-bit float, and that the misrepresentation will lead to large errors for large values of n, but I don't know how to elaborate and explain this sufficiently, or if i might encounter more problems.
Can anyone help me?
Sorry if my english is unclear!
• Sep 28th 2010, 01:03 PM
chisigma
The solution of the difference equation...

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

... is of the form...

$x_{n}= c_{1}\ r_{1}^{n} + c_{2}\ r_{2}^{n}$ (2)

... where $r_{1}$ and $r_{2}$ are the solution of the second order algebraic equation...

$r^{2} - 3\ r +1=0$ (3)

... that are...

$r_{1}= \frac{3-\sqrt{5}}{2}$

$r_{2}= \frac{3+\sqrt{5}}{2}$ (4)

The 'initial conditions' give $c_{1}=1$ $c_{2}=0$ , so that the solution is...

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

Kind regards

$\chi$ $\sigma$