Prove that two recursive sequences are always not zero.

Question

I have the following recursive sequences:

$x_n = x_{n-1} + 2y_{n-1} , x_1 = 1$

$y_n = y_{n-1} - x_{n-1}, y_1 = -1$

where $ x_n,y_n \in \mathbb{Z}$

I have to show that for any $n$ neither $x_n$ or $y_n$ are equal to 0.

Answer 1

HINT: Note that $x_1\bmod 3=1$ and $y_1\bmod 3=2$.

Suppose that $x_{n-1}\bmod 3=1$ and $y_{n-1}\bmod 3=2$; then

$$x_n\bmod 3=(x_{n-1}+2y_{n-1})\bmod 3=(1+4)\bmod 3=2\;,$$

and

$$y_n\bmod 3=(y_{n-1}-x_{n-1})\bmod 3=(2-1)\bmod 3=1\;.$$

What happens when $x_{n-1}\bmod 3=2$ and $y_{n-1}\bmod 3=1$? What is $0\bmod 3$?

Answer 2

hint

$x_n - x_{n-1} = 2y_{n-1}, x_{n-1} - x_{n-2} = 2y_{n-2} \to x_n - 2x_{n-1} + x_{n-2} = 2(y_{n-1} - y_{n-2}) = -2x_{n-2} \to x_n - 2x_{n-1} + 3x_{n-2} = 0 \to x^2 - 2x + 3 = 0$. Can you continue?