Problem 1158

Four (1) Prove by mathematical induction:
$$x_{n}^{2}-5 y_{n}^{2}+4=0 \quad \text { and } \quad 5 y_{n+1} y_{n}-x_{n+1} x_{n}=6 \quad(n=0,1,2, \cdots).$$

First, when $n=0$ and $n=1$, according to the initial values of $\left\{x_{n}\right\}$ and $\left\{y_{n}\right\}$, it can be verified that equation (1) holds.
Assume that equation (1) is correct for $n \leqslant k+1$ $(k \geqslant 0)$. For $n=k+2$,
$$\begin{aligned} x_{k+2}^{2}-5 y_{k+2}^{2}+4 & =\left(3 x_{k+1}-x_{k}\right)^{2}-5\left(3 y_{k+1}-y_{k}\right)^{2}+4 \\ & =9\left(x_{k+1}^{2}-5 y_{k+1}^{2}\right)+\left(x_{k}^{2}-5 y_{k}^{2}\right)+6\left(5 y_{k+1} y_{k}-x_{k+1} x_{k}\right)+4 \\ & =9\left(x_{k+1}^{2}-5 y_{k+1}^{2}+4\right)+\left(x_{k}^{2}-5 y_{k}^{2}+4\right)+6\left(5 y_{k+1} y_{k}-x_{k+1} x_{k}-6\right), \end{aligned}$$

By the induction hypothesis, all three terms in the above equation are 0, so $x_{k+2}^{2}-5 y_{k+2}^{2}+4=0$,
$$\begin{array}{l} 5 y_{k+3} y_{k+2}-x_{k+3} x_{k+2}-6 \\ =5\left(3 y_{k+2}-y_{k+1}\right) y_{k+2}-\left(3 x_{k+2}-x_{k+1}\right) x_{k+2}-6 \\ =3\left(5 y_{k+2}^{2}-x_{k+2}^{2}\right)-\left(5 y_{k+2} y_{k+1}-x_{k+2} x_{k+1}\right)-6 \\ =-3\left(x_{k+2}^{2}-5 y_{k+2}^{2}+4\right)-\left(5 y_{k+2} y_{k+1}-x_{k+2} x_{k+1}-6\right), \end{array}$$

By the induction hypothesis, both terms in the above equation are 0, so $5 y_{k+3} y_{k+2}-x_{k+3} x_{k+2}=0$. Thus, equation (1) holds for $n=k+2$.
Therefore, equation (1) holds for all non-negative integers $n$. So, for all non-negative integers $n$, we have $x_{n}^{2}-5 y_{n}^{2}+4=0$.
(2) Proof by contradiction. Assume there exist positive integers $a, b$ such that $a^{2}-5 b^{2}+4=0$, but there does not exist a non-negative integer $k$ such that $x_{k}=a, y_{k}=b$, and assume that $a, b$ are the smallest such numbers.
We will prove that $\left(\frac{3 a-5 b}{2}, \frac{3 b-a}{2}\right)$ is also a pair of positive integers satisfying the conditions.
First, $a^{2}-b^{2}=4\left(b^{2}-1\right)$ is even, so $a$ and $b$ have the same parity, and $3 a$ and $5 b, 3 b$ and $a$ have the same parity, respectively, so $\frac{3 a-5 b}{2} \in \mathbf{Z}, \frac{3 b-a}{2} \in \mathbf{Z}$. Clearly, if one of $a, b$ is 1, then the other is also 1. This is the first term of $\left\{x_{n}\right\}$ and $\left\{y_{n}\right\}$, which does not satisfy the assumption, so $a \geqslant 2, b \geqslant 2$.

Combining $\frac{3 a-5 b}{2}>0$ (otherwise $a \leqslant \frac{5}{3} b \Rightarrow b^{2} \leqslant 1.8$, contradiction), $\frac{3 b-a}{2}>0$ (otherwise $a \geqslant 3 b \Rightarrow b^{2} \leqslant-1$, contradiction), we have $\frac{3 a-5 b}{2} \in \mathbf{N}^{*}, \frac{3 b-a}{2} \in \mathbf{N}^{*}$.

And $\left(\frac{3 a-5 b}{2}\right)^{2}-5\left(\frac{3 b-a}{2}\right)^{2}+4=a^{2}-5 b^{2}+4=0$, so $\left(\frac{3 a-5 b}{2}, \frac{3 b-a}{2}\right)$ is also a pair of numbers satisfying the conditions.

By $\frac{3 a-5 b}{2}<a$ (otherwise $a \geqslant 5 b \Rightarrow b^{2} \leqslant-\frac{1}{5}$, contradiction), $\frac{3 a-5 b}{2}$ is a number in $\left\{x_{n}\right\}$, otherwise $\left(\frac{3 a-5 b}{2}, \frac{3 b-a}{2}\right)$ is also a pair of positive integers satisfying the conditions, which contradicts the minimality of $a$. So there exists a non-negative integer $k$ such that $x_{k}=\frac{3 a-5 b}{2}$.
The characteristic equation of $\left\{x_{n}\right\}$ and $\left\{y_{n}\right\}$ is the same, $t^{2}-3 t+1=0$, with roots $t_{1,2}=\frac{3 \pm \sqrt{5}}{2}$, so $x_{n}$ and $y_{n}$ both have the form $A \cdot\left(\frac{3+\sqrt{5}}{2}\right)^{n}+B \cdot\left(\frac{3-\sqrt{5}}{2}\right)^{n}$. Using the initial values $x_{0}=y_{0}=1, x_{1}=4, y_{1}=2$, we determine the coefficients by undetermined coefficients, and get
$$\begin{array}{l} x_{n}=\frac{1+\sqrt{5}}{2} \cdot\left(\frac{3+\sqrt{5}}{2}\right)^{n}+\frac{1-\sqrt{5}}{2} \cdot\left(\frac{3-\sqrt{5}}{2}\right)^{n}, \\ y_{n}=\frac{5+\sqrt{5}}{10} \cdot\left(\frac{3+\sqrt{5}}{2}\right)^{n}+\frac{5-\sqrt{5}}{10} \cdot\left(\frac{3-\sqrt{5}}{2}\right)^{n}. \end{array}$$

Here, $n=0,1,2, \cdots$. Thus,
$$\begin{array}{c} \frac{3 a-5 b}{2}=x_{k}=\frac{1+\sqrt{5}}{2} \cdot\left(\frac{3+\sqrt{5}}{2}\right)^{k}+\frac{1-\sqrt{5}}{2} \cdot\left(\frac{3-\sqrt{5}}{2}\right)^{k}, \\ \frac{3 b-a}{2}=y_{k}=\frac{5+\sqrt{5}}{10} \cdot\left(\frac{3+\sqrt{5}}{2}\right)^{k}+\frac{5-\sqrt{5}}{10} \cdot\left(\frac{3-\sqrt{5}}{2}\right)^{k}. \end{array}$$

That is,
$$\begin{array}{l} a=\frac{3}{2} \cdot \frac{3 a-5 b}{2}+\frac{5}{2} \cdot \frac{3 b-a}{2}=\frac{3}{2} x_{k}+\frac{5}{2} y_{k}, \\ b=\frac{1}{2} \cdot \frac{3 a-5 b}{2}+\frac{3}{2} \cdot \frac{3 b-a}{2}=\frac{1}{2} x_{k}+\frac{3}{2} y_{k}. \end{array}$$

Substituting and simplifying, we get
$$\begin{array}{l} a=\frac{1+\sqrt{5}}{2} \cdot\left(\frac{3+\sqrt{5}}{2}\right)^{k+1}+\frac{1-\sqrt{5}}{2} \cdot\left(\frac{3-\sqrt{5}}{2}\right)^{k+1}=x_{k+1}, \\ b=\frac{5+\sqrt{5}}{10} \cdot\left(\frac{3+\sqrt{5}}{2}\right)^{k+1}+\frac{5-\sqrt{5}}{10} \cdot\left(\frac{3-\sqrt{5}}{2}\right)^{k+1}=y_{k+1}. \end{array}$$

That is, there exists $t=k+1$ such that $x_{t}=a, y_{t}=b$.