I am struggling with the following question:
$x_{n+2} - \frac43 x_{n+1} + \frac13 x_n = 1$, $n\ge0$, $x_0 = -\frac32$, $x_1 = -1$ (i)
What happens when you simulate (i) with $64$-bit floating numbers for sufficiently high values of $n$?
The solution should be $\frac{3n}2$ and then overflow. Could someone give an explanation for this solution?
The general solution can be solved from the theory of linear difference equations, using the Ansatz $x_n = z^n$ for the homogeneous part. Inserting into your equation: $$ 3z^2 - 4z + 1 = 0 \implies z = 1, \frac{1}{3}. $$ The constant can be determined by trying the solution for $x_n = Cn$: $$ 3C(n+2) - 4C(n+1) + Cn = 3 \implies C = \frac{3}{2}. $$ So the general solution $$ x_n = A + \frac{B}{3^n} + \frac{3n}{2}, $$ and with your initial conditions you find that $x_0 = A + B = -\frac{3}{2}$ and $x_1 = A + \frac{B}{3} = \frac{1}{2}$ and so $A = \frac{3}{2},B = -3$. You can see that for large $n$ the solution is approaching $x_n \approx \frac{3(n+1)}{2} \approx \frac{3n}{2}$.